Fourier Transform

Introduction.

The Fourier Transform is possibly the most versatile of the integral transforms commonly used in the engineering and scientific fields. Standard examples using the Fourier Transform are:

• smoothing noisy signal waves in digital signal processing
• large integer prime factorisation, where the integers are too large for standard factorisation algorithms.
• analysis of analogue waves: allowing the separation of the different harmonics within the signal.
• analytical work in electrical and mechanical vibrations
• stresses during the bending of beams
• radio waves
• X-Ray diffraction
• analysis of electrical and electronic filters
• antenna theory including beam width, aperture width, beam swinging, etc..
• spectra analysis
• producing simulated filters for statistical information; e.g. for fractal landscapes
• flow of heat through solids.

Indeed, it was during his treatise on The Analytical Theory of Heat (1822) that Fourier first used employed the infinite trigonometric series of sines and cosines, which now bears his name, to represent discontinuous functions. This series is otherwise known as the Fourier Series. The Fourier Transform performs the task of achieving the series through the use of Fourier Analysis. The Fourier Transform is in common use in engineering mathematics, although the transform is most often employed in its discrete form to allow evaluation by computer. | | 244 | Baron Jean Baptiste Joseph Fourier, (1768-1830), was a French mathematician and physicist. He was born in Auxerre in 1768 and educated at the monastery of St-Benoît-sur-Loire. His began his professional life as a tutor at the École Normale (1795), where he had been a student. He also taught at the École Polytechnique in Paris, from 1795 to 1798. In 1798, he joined the campaign of Napoleon in Egypt. After returning to France in 1802, he published important material on Egyptian antiquities and was, until 1815, prefect of Isère département. He was created a baron by Napoleon in 1808. In 1816 he was elected to the Academy of Sciences and in 1827 to the French Academy. His fame rests on his work in mathematics and mathematical physics. In his treatise The Analytical Theory of Heat (1822; translated 1878), he employed a trigonometric series, usually called the Fourier series, by means of which discontinuous functions can be expressed as the sum of an infinite series of sines and cosines.

See also [1]. | | 245 | Baron Jean Baptiste Joseph Fourier, (1768-1830), was a French mathematician and physicist. He was born in Auxerre in 1768 and educated at the monastery of St-Benoît-sur-Loire. His began his professional life as a tutor at the École Normale (1795), where he had been a student. He also taught at the École Polytechnique in Paris, from 1795 to 1798. In 1798, he joined the campaign of Napoleon in Egypt. After returning to France in 1802, he published important material on Egyptian antiquities and was, until 1815, prefect of Isère département. He was created a baron by Napoleon in 1808. In 1816 he was elected to the Academy of Sciences and in 1827 to the French Academy. His fame rests on his work in mathematics and mathematical physics. In his treatise The Analytical Theory of Heat (1822; translated 1878), he employed a trigonometric series, usually called the Fourier series, by means of which discontinuous functions can be expressed as the sum of an infinite series of sines and cosines.

See also Jean Baptiste Joseph Fourier. | | 246 | == Introduction. ==

The Fourier Transform is possibly the most versatile of the integral transforms commonly used in the engineering and scientific fields. Standard examples using the Fourier Transform are:

• smoothing noisy signal waves in digital signal processing
• large integer prime factorisation, where the integers are too large for standard factorisation algorithms.
• analysis of analogue waves: allowing the separation of the different harmonics within the signal.
• analytical work in electrical and mechanical vibrations
• stresses during the bending of beams
• radio waves
• X-Ray diffraction
• analysis of electrical and electronic filters
• antenna theory including beam width, aperture width, beam swinging, etc..
• spectra analysis
• producing simulated filters for statistical information; e.g. for fractal landscapes
• flow of heat through solids.

Indeed, it was during his treatise on The Analytical Theory of Heat (1822) that Fourier first used employed the infinite trigonometric series of sines and cosines, which now bears his name, to represent discontinuous functions. This series is otherwise known as the Fourier Series. The Fourier Transform performs the task of achieving the series through the use of Fourier Analysis. The Fourier Transform is in common use in engineering mathematics, although the transform is most often employed in its discrete form to allow evaluation by computer.

The aim of this project.

The aim of this project is to produce an implementation of the Fast Fourier Transform, which is based on the Cooley-Tukey Algorithm. This algorithm provides an operation efficient method of evaluating the Discrete Fourier Transform. The aims of the project are:

• A procedure is to be implemented, which does not require any knowledge of the workings of the algorithm to be of use to the engineer requiring it.
• An accurate evaluation is to be performed by the transform's procedure.
• A procedure which is as versatile as possible.

Object Oriented Analysis was deemed the most applicable way to produce the final procedure implementing the Fast Fourier Transform. This led to the production of a polynomial library through which the transform would be called. The final aim of the project was to produce a standard polynomial library with the ability to perform the Fourier Transform as simply and efficiently as possible. | | 247 | == Introduction. ==

The Fourier Transform is possibly the most versatile of the integral transforms commonly used in the engineering and scientific fields. Standard examples using the Fourier Transform are:

• smoothing noisy signal waves in digital signal processing
• large integer prime factorisation, where the integers are too large for standard factorisation algorithms.
• analysis of analogue waves: allowing the separation of the different harmonics within the signal.
• analytical work in electrical and mechanical vibrations
• stresses during the bending of beams
• radio waves
• X-Ray diffraction
• analysis of electrical and electronic filters
• antenna theory including beam width, aperture width, beam swinging, etc..
• spectra analysis
• producing simulated filters for statistical information; e.g. for fractal landscapes
• flow of heat through solids.

Indeed, it was during his treatise on The Analytical Theory of Heat (1822) that Fourier first used employed the infinite trigonometric series of sines and cosines, which now bears his name, to represent discontinuous functions. This series is otherwise known as the Fourier Series. The Fourier Transform performs the task of achieving the series through the use of Fourier Analysis. The Fourier Transform is in common use in engineering mathematics, although the transform is most often employed in its discrete form to allow evaluation by computer.

The aim of this project.

The aim of this project is to produce an implementation of the Fast Fourier Transform, which is based on the Cooley-Tukey Algorithm. This algorithm provides an operation efficient method of evaluating the Discrete Fourier Transform. The aims of the project are:

• A procedure is to be implemented, which does not require any knowledge of the workings of the algorithm to be of use to the engineer requiring it.
• An accurate evaluation is to be performed by the transform's procedure.
• A procedure which is as versatile as possible.

Object Oriented Analysis was deemed the most applicable way to produce the final procedure implementing the Fast Fourier Transform. This led to the production of a polynomial library through which the transform would be called. The final aim of the project was to produce a standard polynomial library with the ability to perform the Fourier Transform as simply and efficiently as possible.

The aim of this report.

This report covers the progress of this project from the initial background research and design stages to the implementation and testing of the final produce and library. It provides the reader with the information used to produce the Fast Fourier Transform procedure presented, with some analysis as to the efficiency and accuracy of the Fast Fourier Transform algorithm used. The project was run with four main stages:

• Planning with the resources available for completing the project.
• Design of the algorithm and polynomial classes, based on research applicable to the problem.
• Implementation of the algorithms.
• Testing of the implementation in terms of accuracy and efficiency.

It is within this structure that the report will be presented. Section 2 covers the Planning of the project, with a short outline of what is to be achieved during the time period. Sections 3 and 4 go into the and Background research of the algorithms used to implement the Fast Fourier Transform. Object Oriented Analysis is performed in Section 5 with the Object Oriented Design being discussed in section 6. Implementation of the algorithms is performed in section 7, and the Testing in section 8. The Conclusions of the Implementation of the Fast Fourier Transform are given in the final section, section 9. | | 248 | == Introduction. ==

The Fourier Transform is possibly the most versatile of the integral transforms commonly used in the engineering and scientific fields. Standard examples using the Fourier Transform are:

• smoothing noisy signal waves in digital signal processing
• large integer prime factorisation, where the integers are too large for standard factorisation algorithms.
• analysis of analogue waves: allowing the separation of the different harmonics within the signal.
• analytical work in electrical and mechanical vibrations
• stresses during the bending of beams
• radio waves
• X-Ray diffraction
• analysis of electrical and electronic filters
• antenna theory including beam width, aperture width, beam swinging, etc..
• spectra analysis
• producing simulated filters for statistical information; e.g. for fractal landscapes
• flow of heat through solids.

Indeed, it was during his treatise on The Analytical Theory of Heat (1822) that Fourier first used employed the infinite trigonometric series of sines and cosines, which now bears his name, to represent discontinuous functions. This series is otherwise known as the Fourier Series. The Fourier Transform performs the task of achieving the series through the use of Fourier Analysis. The Fourier Transform is in common use in engineering mathematics, although the transform is most often employed in its discrete form to allow evaluation by computer.

The aim of this project.

The aim of this project is to produce an implementation of the Fast Fourier Transform, which is based on the Cooley-Tukey Algorithm. This algorithm provides an operation efficient method of evaluating the Discrete Fourier Transform. The aims of the project are:

• A procedure is to be implemented, which does not require any knowledge of the workings of the algorithm to be of use to the engineer requiring it.
• An accurate evaluation is to be performed by the transform's procedure.
• A procedure which is as versatile as possible.

Object Oriented Analysis was deemed the most applicable way to produce the final procedure implementing the Fast Fourier Transform. This led to the production of a polynomial library through which the transform would be called. The final aim of the project was to produce a standard polynomial library with the ability to perform the Fourier Transform as simply and efficiently as possible.

The aim of this report.

This report covers the progress of this project from the initial background research and design stages to the implementation and testing of the final produce and library. It provides the reader with the information used to produce the Fast Fourier Transform procedure presented, with some analysis as to the efficiency and accuracy of the Fast Fourier Transform algorithm used. The project was run with four main stages:

• Planning with the resources available for completing the project.
• Design of the algorithm and polynomial classes, based on research applicable to the problem.
• Implementation of the algorithms.
• Testing of the implementation in terms of accuracy and efficiency.

It is within this structure that the report will be presented. Section 2 covers the Planning of the project, with a short outline of what is to be achieved during the time period. Sections 3 and 4 go into the and Background research of the algorithms used to implement the Fast Fourier Transform. Object Oriented Analysis is performed in Section 5 with the Object Oriented Design being discussed in section 6. Implementation of the algorithms is performed in section 7, and the Testing in section 8. The Conclusions of the Implementation of the Fast Fourier Transform are given in the final section, section 9.

Design

This constitutes most of the work carried out for the Implementation of the Fast Fourier Transform. Before any formal design strategy was constructed, the Fourier Transform was investigated.

Background research

Transforms

Transforms are used to solve mathematical problems that are difficult to solve otherwise. A transform is defined thus: transforms are tools for altering the problem into one that may be easily solved. After the transformed problem has been solved, an inverse is applied to gain the answer for the original problem. The Fourier Transform is one such tool. The Fourier Transform is a versatile transform. Fourier first used the method for the solution of heat equations in solids. There are many situations in which the Fourier Transform is applicable. One example of the use of the Fourier Transform is for smoothing noisy sound waveforms. | | 249 | == Introduction. ==

The Fourier Transform is possibly the most versatile of the integral transforms commonly used in the engineering and scientific fields. Standard examples using the Fourier Transform are:

• smoothing noisy signal waves in digital signal processing
• large integer prime factorisation, where the integers are too large for standard factorisation algorithms.
• analysis of analogue waves: allowing the separation of the different harmonics within the signal.
• analytical work in electrical and mechanical vibrations
• stresses during the bending of beams
• radio waves
• X-Ray diffraction
• analysis of electrical and electronic filters
• antenna theory including beam width, aperture width, beam swinging, etc..
• spectra analysis
• producing simulated filters for statistical information; e.g. for fractal landscapes
• flow of heat through solids.

Indeed, it was during his treatise on The Analytical Theory of Heat (1822) that Fourier first used employed the infinite trigonometric series of sines and cosines, which now bears his name, to represent discontinuous functions. This series is otherwise known as the Fourier Series. The Fourier Transform performs the task of achieving the series through the use of Fourier Analysis. The Fourier Transform is in common use in engineering mathematics, although the transform is most often employed in its discrete form to allow evaluation by computer.

The aim of this project.

The aim of this project is to produce an implementation of the Fast Fourier Transform, which is based on the Cooley-Tukey Algorithm. This algorithm provides an operation efficient method of evaluating the Discrete Fourier Transform. The aims of the project are:

• A procedure is to be implemented, which does not require any knowledge of the workings of the algorithm to be of use to the engineer requiring it.
• An accurate evaluation is to be performed by the transform's procedure.
• A procedure which is as versatile as possible.

Object Oriented Analysis was deemed the most applicable way to produce the final procedure implementing the Fast Fourier Transform. This led to the production of a polynomial library through which the transform would be called. The final aim of the project was to produce a standard polynomial library with the ability to perform the Fourier Transform as simply and efficiently as possible.

The aim of this report.

This report covers the progress of this project from the initial background research and design stages to the implementation and testing of the final produce and library. It provides the reader with the information used to produce the Fast Fourier Transform procedure presented, with some analysis as to the efficiency and accuracy of the Fast Fourier Transform algorithm used. The project was run with four main stages:

• Planning with the resources available for completing the project.
• Design of the algorithm and polynomial classes, based on research applicable to the problem.
• Implementation of the algorithms.
• Testing of the implementation in terms of accuracy and efficiency.

It is within this structure that the report will be presented. Section 2 covers the Planning of the project, with a short outline of what is to be achieved during the time period. Sections 3 and 4 go into the and Background research of the algorithms used to implement the Fast Fourier Transform. Object Oriented Analysis is performed in Section 5 with the Object Oriented Design being discussed in section 6. Implementation of the algorithms is performed in section 7, and the Testing in section 8. The Conclusions of the Implementation of the Fast Fourier Transform are given in the final section, section 9.

Design

This constitutes most of the work carried out for the Implementation of the Fast Fourier Transform. Before any formal design strategy was constructed, the Fourier Transform was investigated.

Background research

Transforms

Transforms are used to solve mathematical problems that are difficult to solve otherwise. A transform is defined thus: transforms are tools for altering the problem into one that may be easily solved. After the transformed problem has been solved, an inverse is applied to gain the answer for the original problem. The Fourier Transform is one such tool. The Fourier Transform is a versatile transform. Fourier first used the method for the solution of heat equations in solids. There are many situations in which the Fourier Transform is applicable. One example of the use of the Fourier Transform is for smoothing noisy sound waveforms.

The Fourier Transform

The Fourier Transform typically acts on polynomials. Polynomials are series of products of a constant and a power of a variable. A polynomial, f(x), may therefore be described as

Please insert the formula

The degree of the polynomial is the value of the highest power of x for which an ¹ 0. The polynomial f(x) may then be described by an ordered set {a0, a1, … , an} where n is the degree of the polynomial. Hence, n+1 coefficients are required to define the polynomial f(x) completely. This is not the only method of describing polynomials. A polynomial may also be described by the values of f(x) calculated by the series for different values of x. A minimum of n+1 different values of x must be calculated in order to describe the polynomial f(x) uniquely. | | 250 | == Introduction. ==

The Fourier Transform is possibly the most versatile of the integral transforms commonly used in the engineering and scientific fields. Standard examples using the Fourier Transform are:

• smoothing noisy signal waves in digital signal processing
• large integer prime factorisation, where the integers are too large for standard factorisation algorithms.
• analysis of analogue waves: allowing the separation of the different harmonics within the signal.
• analytical work in electrical and mechanical vibrations
• stresses during the bending of beams
• radio waves
• X-Ray diffraction
• analysis of electrical and electronic filters
• antenna theory including beam width, aperture width, beam swinging, etc..
• spectra analysis
• producing simulated filters for statistical information; e.g. for fractal landscapes
• flow of heat through solids.

Indeed, it was during his treatise on The Analytical Theory of Heat (1822) that Fourier first used employed the infinite trigonometric series of sines and cosines, which now bears his name, to represent discontinuous functions. This series is otherwise known as the Fourier Series. The Fourier Transform performs the task of achieving the series through the use of Fourier Analysis. The Fourier Transform is in common use in engineering mathematics, although the transform is most often employed in its discrete form to allow evaluation by computer.

The aim of this project.

The aim of this project is to produce an implementation of the Fast Fourier Transform, which is based on the Cooley-Tukey Algorithm. This algorithm provides an operation efficient method of evaluating the Discrete Fourier Transform. The aims of the project are:

• A procedure is to be implemented, which does not require any knowledge of the workings of the algorithm to be of use to the engineer requiring it.
• An accurate evaluation is to be performed by the transform's procedure.
• A procedure which is as versatile as possible.

Object Oriented Analysis was deemed the most applicable way to produce the final procedure implementing the Fast Fourier Transform. This led to the production of a polynomial library through which the transform would be called. The final aim of the project was to produce a standard polynomial library with the ability to perform the Fourier Transform as simply and efficiently as possible.

The aim of this report.

This report covers the progress of this project from the initial background research and design stages to the implementation and testing of the final produce and library. It provides the reader with the information used to produce the Fast Fourier Transform procedure presented, with some analysis as to the efficiency and accuracy of the Fast Fourier Transform algorithm used. The project was run with four main stages:

• Planning with the resources available for completing the project.
• Design of the algorithm and polynomial classes, based on research applicable to the problem.
• Implementation of the algorithms.
• Testing of the implementation in terms of accuracy and efficiency.

It is within this structure that the report will be presented. Section 2 covers the Planning of the project, with a short outline of what is to be achieved during the time period. Sections 3 and 4 go into the and Background research of the algorithms used to implement the Fast Fourier Transform. Object Oriented Analysis is performed in Section 5 with the Object Oriented Design being discussed in section 6. Implementation of the algorithms is performed in section 7, and the Testing in section 8. The Conclusions of the Implementation of the Fast Fourier Transform are given in the final section, section 9.

Design

This constitutes most of the work carried out for the Implementation of the Fast Fourier Transform. Before any formal design strategy was constructed, the Fourier Transform was investigated.

Background research

Transforms

Transforms are used to solve mathematical problems that are difficult to solve otherwise. A transform is defined thus: transforms are tools for altering the problem into one that may be easily solved. After the transformed problem has been solved, an inverse is applied to gain the answer for the original problem. The Fourier Transform is one such tool. The Fourier Transform is a versatile transform. Fourier first used the method for the solution of heat equations in solids. There are many situations in which the Fourier Transform is applicable. One example of the use of the Fourier Transform is for smoothing noisy sound waveforms.

The Fourier Transform

The Fourier Transform typically acts on polynomials. Polynomials are series of products of a constant and a power of a variable. A polynomial, f(x), may therefore be described as

Please insert the formula

The degree of the polynomial is the value of the highest power of x for which an ¹ 0. The polynomial f(x) may then be described by an ordered set {a0, a1, … , an} where n is the degree of the polynomial. Hence, n+1 coefficients are required to define the polynomial f(x) completely. This is not the only method of describing polynomials. A polynomial may also be described by the values of f(x) calculated by the series for different values of x. A minimum of n+1 different values of x must be calculated in order to describe the polynomial f(x) uniquely.

And the diagram

The Continuous and Discrete Fourier Transforms.

The transform used in Figure 8.1 is the Fourier Transform that is calculated using the following formulae, which are derived and proved in Appendix D.

The transform and its inverse

The Fourier Transform takes a polynomial described in terms of coefficients, f(x), and returns F(a), a polynomial described in terms of values of f(x). The Inverse Fourier Transform takes F(a), a polynomial described in terms of values of f(x), and returns f(x), a polynomial described in terms of coefficients. | | 251 | == Introduction. ==

The Fourier Transform is possibly the most versatile of the integral transforms commonly used in the engineering and scientific fields. Standard examples using the Fourier Transform are:

• smoothing noisy signal waves in digital signal processing
• large integer prime factorisation, where the integers are too large for standard factorisation algorithms.
• analysis of analogue waves: allowing the separation of the different harmonics within the signal.
• analytical work in electrical and mechanical vibrations
• stresses during the bending of beams
• radio waves
• X-Ray diffraction
• analysis of electrical and electronic filters
• antenna theory including beam width, aperture width, beam swinging, etc..
• spectra analysis
• producing simulated filters for statistical information; e.g. for fractal landscapes
• flow of heat through solids.

Indeed, it was during his treatise on The Analytical Theory of Heat (1822) that Fourier first used employed the infinite trigonometric series of sines and cosines, which now bears his name, to represent discontinuous functions. This series is otherwise known as the Fourier Series. The Fourier Transform performs the task of achieving the series through the use of Fourier Analysis. The Fourier Transform is in common use in engineering mathematics, although the transform is most often employed in its discrete form to allow evaluation by computer.

The aim of this project.

The aim of this project is to produce an implementation of the Fast Fourier Transform, which is based on the Cooley-Tukey Algorithm. This algorithm provides an operation efficient method of evaluating the Discrete Fourier Transform. The aims of the project are:

• A procedure is to be implemented, which does not require any knowledge of the workings of the algorithm to be of use to the engineer requiring it.
• An accurate evaluation is to be performed by the transform's procedure.
• A procedure which is as versatile as possible.

Object Oriented Analysis was deemed the most applicable way to produce the final procedure implementing the Fast Fourier Transform. This led to the production of a polynomial library through which the transform would be called. The final aim of the project was to produce a standard polynomial library with the ability to perform the Fourier Transform as simply and efficiently as possible.

The aim of this report.

This report covers the progress of this project from the initial background research and design stages to the implementation and testing of the final produce and library. It provides the reader with the information used to produce the Fast Fourier Transform procedure presented, with some analysis as to the efficiency and accuracy of the Fast Fourier Transform algorithm used. The project was run with four main stages:

• Planning with the resources available for completing the project.
• Design of the algorithm and polynomial classes, based on research applicable to the problem.
• Implementation of the algorithms.
• Testing of the implementation in terms of accuracy and efficiency.

It is within this structure that the report will be presented. Section 2 covers the Planning of the project, with a short outline of what is to be achieved during the time period. Sections 3 and 4 go into the and Background research of the algorithms used to implement the Fast Fourier Transform. Object Oriented Analysis is performed in Section 5 with the Object Oriented Design being discussed in section 6. Implementation of the algorithms is performed in section 7, and the Testing in section 8. The Conclusions of the Implementation of the Fast Fourier Transform are given in the final section, section 9.

Design

This constitutes most of the work carried out for the Implementation of the Fast Fourier Transform. Before any formal design strategy was constructed, the Fourier Transform was investigated.

Background research

Transforms

Transforms are used to solve mathematical problems that are difficult to solve otherwise. A transform is defined thus: transforms are tools for altering the problem into one that may be easily solved. After the transformed problem has been solved, an inverse is applied to gain the answer for the original problem. The Fourier Transform is one such tool. The Fourier Transform is a versatile transform. Fourier first used the method for the solution of heat equations in solids. There are many situations in which the Fourier Transform is applicable. One example of the use of the Fourier Transform is for smoothing noisy sound waveforms.

The Fourier Transform

The Fourier Transform typically acts on polynomials. Polynomials are series of products of a constant and a power of a variable. A polynomial, f(x), may therefore be described as

Please insert the formula

The degree of the polynomial is the value of the highest power of x for which an ¹ 0. The polynomial f(x) may then be described by an ordered set {a0, a1, … , an} where n is the degree of the polynomial. Hence, n+1 coefficients are required to define the polynomial f(x) completely. This is not the only method of describing polynomials. A polynomial may also be described by the values of f(x) calculated by the series for different values of x. A minimum of n+1 different values of x must be calculated in order to describe the polynomial f(x) uniquely.

And the diagram

The Continuous and Discrete Fourier Transforms. P7

The transform used in Figure 8.1 is the Fourier Transform that is calculated using the following formulae, which are derived and proved in Appendix D.

The transform and its inverse

The Fourier Transform takes a polynomial described in terms of coefficients, f(x), and returns F(a), a polynomial described in terms of values of f(x). The Inverse Fourier Transform takes F(a), a polynomial described in terms of values of f(x), and returns f(x), a polynomial described in terms of coefficients. | | 252 | {{#security:*|803245868}}

Introduction.

The Fourier Transform is possibly the most versatile of the integral transforms commonly used in the engineering and scientific fields. Standard examples using the Fourier Transform are:

• smoothing noisy signal waves in digital signal processing
• large integer prime factorisation, where the integers are too large for standard factorisation algorithms.
• analysis of analogue waves: allowing the separation of the different harmonics within the signal.
• analytical work in electrical and mechanical vibrations
• stresses during the bending of beams
• radio waves
• X-Ray diffraction
• analysis of electrical and electronic filters
• antenna theory including beam width, aperture width, beam swinging, etc..
• spectra analysis
• producing simulated filters for statistical information; e.g. for fractal landscapes
• flow of heat through solids.

Indeed, it was during his treatise on The Analytical Theory of Heat (1822) that Fourier first used employed the infinite trigonometric series of sines and cosines, which now bears his name, to represent discontinuous functions. This series is otherwise known as the Fourier Series. The Fourier Transform performs the task of achieving the series through the use of Fourier Analysis. The Fourier Transform is in common use in engineering mathematics, although the transform is most often employed in its discrete form to allow evaluation by computer.

The aim of this project.

The aim of this project is to produce an implementation of the Fast Fourier Transform, which is based on the Cooley-Tukey Algorithm. This algorithm provides an operation efficient method of evaluating the Discrete Fourier Transform. The aims of the project are:

• A procedure is to be implemented, which does not require any knowledge of the workings of the algorithm to be of use to the engineer requiring it.
• An accurate evaluation is to be performed by the transform's procedure.
• A procedure which is as versatile as possible.

Object Oriented Analysis was deemed the most applicable way to produce the final procedure implementing the Fast Fourier Transform. This led to the production of a polynomial library through which the transform would be called. The final aim of the project was to produce a standard polynomial library with the ability to perform the Fourier Transform as simply and efficiently as possible.

The aim of this report.

This report covers the progress of this project from the initial background research and design stages to the implementation and testing of the final produce and library. It provides the reader with the information used to produce the Fast Fourier Transform procedure presented, with some analysis as to the efficiency and accuracy of the Fast Fourier Transform algorithm used. The project was run with four main stages:

• Planning with the resources available for completing the project.
• Design of the algorithm and polynomial classes, based on research applicable to the problem.
• Implementation of the algorithms.
• Testing of the implementation in terms of accuracy and efficiency.

It is within this structure that the report will be presented. Section 2 covers the Planning of the project, with a short outline of what is to be achieved during the time period. Sections 3 and 4 go into the and Background research of the algorithms used to implement the Fast Fourier Transform. Object Oriented Analysis is performed in Section 5 with the Object Oriented Design being discussed in section 6. Implementation of the algorithms is performed in section 7, and the Testing in section 8. The Conclusions of the Implementation of the Fast Fourier Transform are given in the final section, section 9.

Design

This constitutes most of the work carried out for the Implementation of the Fast Fourier Transform. Before any formal design strategy was constructed, the Fourier Transform was investigated.

Background research

Transforms

Transforms are used to solve mathematical problems that are difficult to solve otherwise. A transform is defined thus: transforms are tools for altering the problem into one that may be easily solved. After the transformed problem has been solved, an inverse is applied to gain the answer for the original problem. The Fourier Transform is one such tool. The Fourier Transform is a versatile transform. Fourier first used the method for the solution of heat equations in solids. There are many situations in which the Fourier Transform is applicable. One example of the use of the Fourier Transform is for smoothing noisy sound waveforms.

The Fourier Transform

The Fourier Transform typically acts on polynomials. Polynomials are series of products of a constant and a power of a variable. A polynomial, f(x), may therefore be described as

Please insert the formula

The degree of the polynomial is the value of the highest power of x for which an ¹ 0. The polynomial f(x) may then be described by an ordered set {a0, a1, … , an} where n is the degree of the polynomial. Hence, n+1 coefficients are required to define the polynomial f(x) completely. This is not the only method of describing polynomials. A polynomial may also be described by the values of f(x) calculated by the series for different values of x. A minimum of n+1 different values of x must be calculated in order to describe the polynomial f(x) uniquely.

And the diagram

The Continuous and Discrete Fourier Transforms. P7

The transform used in Figure 8.1 is the Fourier Transform that is calculated using the following formulae, which are derived and proved in Appendix D.

The transform and its inverse

The Fourier Transform takes a polynomial described in terms of coefficients, f(x), and returns F(a), a polynomial described in terms of values of f(x). The Inverse Fourier Transform takes F(a), a polynomial described in terms of values of f(x), and returns f(x), a polynomial described in terms of coefficients.