What kind of hardware implements Fourier transform?Harmonic and Fourier transformWhy more bandwidth means...

Why avoid shared user accounts?

Difference between `vector<int> v;` and `vector<int> v = vector<int>();`

Why do neural networks need so many training examples to perform?

My cat mixes up the floors in my building. How can I help him?

Why did other German political parties disband so fast when Hitler was appointed chancellor?

How would an AI self awareness kill switch work?

If I deleted a game I lost the disc for, can I reinstall it digitally?

Why is working on the same position for more than 15 years not a red flag?

How can I get my players to come to the game session after agreeing to a date?

How to say "Brexit" in Latin?

One Half of Ten; A Riddle

Caruana vs Carlsen game 10 (WCC) why not 18...Nxb6?

Pronunciation of umlaut vowels in the history of German

Which password policy is more secure: one password of length 9 vs. two passwords each of length 8?

How can my powered armor quickly replace its ceramic plates?

What's a good word to describe a public place that looks like it wouldn't be rough?

Roman Numerals equation 1

What is better: yes / no radio, or simple checkbox?

Cookies - Should the toggles be on?

what does しにみえてる mean?

Lick explanation

In Linux what happens if 1000 files in a directory are moved to another location while another 300 files were added to the source directory?

It took me a lot of time to make this, pls like. (YouTube Comments #1)

Porting Linux to another platform requirements



What kind of hardware implements Fourier transform?


Harmonic and Fourier transformWhy more bandwidth means more bit rate per second?Fourier TransformFourier Transform in real lifeFourier transform and signal envelopeFourier Transform using pairs tableFourier TransformFourier Transform - convolution theoremCoefficients and harmonics of a PWM signalFourier Transform vs. Laplace Transform?













1












$begingroup$


I looked around online but I found nothing relevant. It is very difficult for an electronic device to decompose a signal in different frequencies.



How this is done at the bare metal level?



Any suggested source or comment will be very helpful










share|improve this question









$endgroup$












  • $begingroup$
    A lot of the time you don't need FT to do signal processing, especially filtering. E.g. you can use passive or active filters which depend on the properties of capacitors and inductors. Even in the digital domain, when working with values out of ADC, you can go without FT for some tasks (e.g. see exponential smoothing).
    $endgroup$
    – anrieff
    3 hours ago


















1












$begingroup$


I looked around online but I found nothing relevant. It is very difficult for an electronic device to decompose a signal in different frequencies.



How this is done at the bare metal level?



Any suggested source or comment will be very helpful










share|improve this question









$endgroup$












  • $begingroup$
    A lot of the time you don't need FT to do signal processing, especially filtering. E.g. you can use passive or active filters which depend on the properties of capacitors and inductors. Even in the digital domain, when working with values out of ADC, you can go without FT for some tasks (e.g. see exponential smoothing).
    $endgroup$
    – anrieff
    3 hours ago
















1












1








1





$begingroup$


I looked around online but I found nothing relevant. It is very difficult for an electronic device to decompose a signal in different frequencies.



How this is done at the bare metal level?



Any suggested source or comment will be very helpful










share|improve this question









$endgroup$




I looked around online but I found nothing relevant. It is very difficult for an electronic device to decompose a signal in different frequencies.



How this is done at the bare metal level?



Any suggested source or comment will be very helpful







power-electronics hardware fourier






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked 3 hours ago









veronikaveronika

13018




13018












  • $begingroup$
    A lot of the time you don't need FT to do signal processing, especially filtering. E.g. you can use passive or active filters which depend on the properties of capacitors and inductors. Even in the digital domain, when working with values out of ADC, you can go without FT for some tasks (e.g. see exponential smoothing).
    $endgroup$
    – anrieff
    3 hours ago




















  • $begingroup$
    A lot of the time you don't need FT to do signal processing, especially filtering. E.g. you can use passive or active filters which depend on the properties of capacitors and inductors. Even in the digital domain, when working with values out of ADC, you can go without FT for some tasks (e.g. see exponential smoothing).
    $endgroup$
    – anrieff
    3 hours ago


















$begingroup$
A lot of the time you don't need FT to do signal processing, especially filtering. E.g. you can use passive or active filters which depend on the properties of capacitors and inductors. Even in the digital domain, when working with values out of ADC, you can go without FT for some tasks (e.g. see exponential smoothing).
$endgroup$
– anrieff
3 hours ago






$begingroup$
A lot of the time you don't need FT to do signal processing, especially filtering. E.g. you can use passive or active filters which depend on the properties of capacitors and inductors. Even in the digital domain, when working with values out of ADC, you can go without FT for some tasks (e.g. see exponential smoothing).
$endgroup$
– anrieff
3 hours ago












3 Answers
3






active

oldest

votes


















6












$begingroup$

Devices using the Fourier Transform




It is very difficult for an electronic device to decompose a signal in different frequencies.




It's not.



There's actually quite a few devices that do that, explicitly.



First of all, you'll have to make a difference between the continuous Fourier transform (which you probably know as $mathcal Fleft{x(t)right}(f)=int_{-infty}^{infty} x(t)e^{j2pi f t},mathrm dt$) and the Digital Fourier Transform (DFT), which is what you can do with a sampled signal.



For both, there's devices that implement these.



Continuous Fourier Transform



There's little in the ways of actual need for this in digital electronics – digital signals are sampled, so you'd use the DFT.



In optics and photonics you'll notice that there's an actual chance to get perfectly periodic things for a "large" (read as: nearly as infinite as the integral above) length. Effectively, an acousto-optic element can be excited with one or multiple tones, and it will have the same correlating effects as the integral above. You don't have to look at 2018's Physics Nobel Prize winners to find an example of Fourier Optics.



Discrete Fourier Transform



This is really all over the place; it's such a standard processing step that as a communication engineer, we often even forget where it is.



So, this list is far less than complete; just examples:





  • Equalizers: It's pretty easy building a digital audio equalizer with a DFT. Typically, the zero-forcing equalizer type for communication systems uses a DFT to find the frequency domain representation of the channel necessary to be "removed", inverts that and uses the IDFT to get back that back to time domain to be used as taps in a FIR filter.


  • Antenna Arrays / Beamsteering: If you have an array of antennas in fixed distance from each other, you can steer the beam of these antennas, by calculating the DFT of the "directional vector" you'd like to achieve and use the result as complex coefficients to be multiplied with the transmit signal that you distribute to these antennas. Real-world MIMO systems do that.


  • Direction Finding: What works in transmit direction works exactly the same, but reverse, in receive direction: Get a signal for each of your antennas in your array, find the complex factors between these signals, do an IDFT, get a vector containing the info how power came from which direction. Easy! And done for estimation where aircraft are, where Wifi communication partners are, submarines (though there it's not antennas but underwater microphones)…


  • Channelization: Satellites in space are expensive, so multiple TV programs need to be uplinked to one satellite. You can use a DFT (especially in an Polyphase Filterbank) to put multiple channels in one uplink, or to isolate individual channels from one wideband signal. That's not a domain of TV; it happens in audio processing, medical imaging, ultrasonic analysis, Radio broadcasting…)


  • Data Encoding for multicarrier systems: To combat the problems of wide channels (which you need if you want to transport many bits per second), namely the need for complex equalizers, you'd want to chop up your channel in many small channels (see "channelization" above). However, you can understand the DFT alone as Filterbank for frequency-shifted time-domain-rectangular filters. The nice thing about that is that these channels are very tightly packed. The other nice thing is that the convolution with the channel reduces to a point-wise multiplication which is super simple to revert. We call that method OFDM, and all Wifi, LTE, 5G, WiMax, ATSC, DVB-T, Digital Audio Broadcasting, DSL, and many more systems use that.


  • Efficient Filtering: A FIR filter is a convolution with the filter impulse response in time domain. As such, it uses a lot of operations per output sample – it's very computationally intense. You can greatly reduce that effort when you implement fast convolution, which is based on DFT'ing sections of input samples, mutliplying them with the DFT of the impulse response in frequency domain, overlapping with previous segments, and back-transformation to time domain. That's so handy that it's used in almost all systems that have long FIR filters (and "long" might start with so benign numbers as "16 taps").


  • Radar: Classical automotive radars use self-modulating FMCW radars; to get a picture of both the relative speed and distance of reflectors observed by that, you typically do a two-dimensional DFT (which really is just DFT'ing all columns of a matrix and afterwards all rows of the result).


  • Audio and Image/Video Compression: Though JPEG uses the Discrete Cosine Transform, not the DFT itself, there's ample of codecs that mechanism which at least use significant parts of a DFT.


Note that the above list only contains things that do DFTs during operation. You can be 100% sure that during design of anything remotely related to RF, especially antenas, mixers, amplifiers, (de)modulators, a lot of Fourier Transforms / Spectral analysis was involved. Same goes for audio device design, any high-speed data link design, image analysis…



How is it done?



I'll just address the DFT here.



Usually, that's implemented as an FFT, Fast Fourier Transform. That's one of the most important algorithmic discoveries of the 20th century, so I will spare but few words on it, because there's literally thousands of articles out there that explain the FFT.



You go in and look at the $e^{j2pi frac nN k}$ multipliers of a DFT. You'll notice that these can basically be understood as ${e^{j2pi frac 1N k}}^n=W^n$; and there you have your twiddle factor. Now you avoid calculating coefficients that you've already calculated, and just swap a sign where necessary.



That way, you can reduce the complexity of a DFT from the $N^2$ (which would be the complexity if you implemented the DFT as the naive sum) to something in the order of $Nlog N$ – a huge win, even for relatively small $N$.



It's relatively straightforward to implement that in hardware, if you can get your whole input vector at once – you get $log N$ as a combinatorial depth and fixed coefficients at every step. The trick is knowing how (whether) to pipeline the individual layers, and how to use the specific hardware type you have (ASIC? FPGA? FPGA with hardware multipliers?). You can basically piece together $N=2^l$-length transform only from what we call Butterflies, which you'll recognize once you read about the FFT.



In software, the principle is the same, but you need to know how to multi-thread very large transforms, and how to access memory as fast as possible by utilizing your CPU caches optimally.



However, for both hardware and software, there's libraries that you'd just use to calculate the DFT (FFT). For Hardware, that usually comes from your FPGA vendor (e.g. Altera/Intel, Xilinx, Lattice…) , or a large ASIC design tool company (Cadence) or your ASIC house.






share|improve this answer











$endgroup$













  • $begingroup$
    Impressive dedication to your art, agree that 'long' is O(16) for FIR filters.
    $endgroup$
    – Neil_UK
    7 mins ago



















0












$begingroup$

That's basically what a spectrum analyzer does:



https://www.electronics-notes.com/articles/test-methods/spectrum-analyzer/realtime-spectrum-analyser.php






share|improve this answer









$endgroup$









  • 2




    $begingroup$
    No it's not what a spectrum analyzer does in general. Some (many) spectrum analyzers have an FFT mode, but even then, what the spectrum analyzer shows you is a PSD estimate, not a Fourier transform.
    $endgroup$
    – Marcus Müller
    2 hours ago



















0












$begingroup$

You can't get much more "bare metal" and "hardware" than a set of vibrating reeds.



http://www.stichtco.com/freq_met.htm



So what hardware does a fourier transform, a bunch of resonant systems can do that






share|improve this answer









$endgroup$













    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("schematics", function () {
    StackExchange.schematics.init();
    });
    }, "cicuitlab");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "135"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2felectronics.stackexchange.com%2fquestions%2f425008%2fwhat-kind-of-hardware-implements-fourier-transform%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    6












    $begingroup$

    Devices using the Fourier Transform




    It is very difficult for an electronic device to decompose a signal in different frequencies.




    It's not.



    There's actually quite a few devices that do that, explicitly.



    First of all, you'll have to make a difference between the continuous Fourier transform (which you probably know as $mathcal Fleft{x(t)right}(f)=int_{-infty}^{infty} x(t)e^{j2pi f t},mathrm dt$) and the Digital Fourier Transform (DFT), which is what you can do with a sampled signal.



    For both, there's devices that implement these.



    Continuous Fourier Transform



    There's little in the ways of actual need for this in digital electronics – digital signals are sampled, so you'd use the DFT.



    In optics and photonics you'll notice that there's an actual chance to get perfectly periodic things for a "large" (read as: nearly as infinite as the integral above) length. Effectively, an acousto-optic element can be excited with one or multiple tones, and it will have the same correlating effects as the integral above. You don't have to look at 2018's Physics Nobel Prize winners to find an example of Fourier Optics.



    Discrete Fourier Transform



    This is really all over the place; it's such a standard processing step that as a communication engineer, we often even forget where it is.



    So, this list is far less than complete; just examples:





    • Equalizers: It's pretty easy building a digital audio equalizer with a DFT. Typically, the zero-forcing equalizer type for communication systems uses a DFT to find the frequency domain representation of the channel necessary to be "removed", inverts that and uses the IDFT to get back that back to time domain to be used as taps in a FIR filter.


    • Antenna Arrays / Beamsteering: If you have an array of antennas in fixed distance from each other, you can steer the beam of these antennas, by calculating the DFT of the "directional vector" you'd like to achieve and use the result as complex coefficients to be multiplied with the transmit signal that you distribute to these antennas. Real-world MIMO systems do that.


    • Direction Finding: What works in transmit direction works exactly the same, but reverse, in receive direction: Get a signal for each of your antennas in your array, find the complex factors between these signals, do an IDFT, get a vector containing the info how power came from which direction. Easy! And done for estimation where aircraft are, where Wifi communication partners are, submarines (though there it's not antennas but underwater microphones)…


    • Channelization: Satellites in space are expensive, so multiple TV programs need to be uplinked to one satellite. You can use a DFT (especially in an Polyphase Filterbank) to put multiple channels in one uplink, or to isolate individual channels from one wideband signal. That's not a domain of TV; it happens in audio processing, medical imaging, ultrasonic analysis, Radio broadcasting…)


    • Data Encoding for multicarrier systems: To combat the problems of wide channels (which you need if you want to transport many bits per second), namely the need for complex equalizers, you'd want to chop up your channel in many small channels (see "channelization" above). However, you can understand the DFT alone as Filterbank for frequency-shifted time-domain-rectangular filters. The nice thing about that is that these channels are very tightly packed. The other nice thing is that the convolution with the channel reduces to a point-wise multiplication which is super simple to revert. We call that method OFDM, and all Wifi, LTE, 5G, WiMax, ATSC, DVB-T, Digital Audio Broadcasting, DSL, and many more systems use that.


    • Efficient Filtering: A FIR filter is a convolution with the filter impulse response in time domain. As such, it uses a lot of operations per output sample – it's very computationally intense. You can greatly reduce that effort when you implement fast convolution, which is based on DFT'ing sections of input samples, mutliplying them with the DFT of the impulse response in frequency domain, overlapping with previous segments, and back-transformation to time domain. That's so handy that it's used in almost all systems that have long FIR filters (and "long" might start with so benign numbers as "16 taps").


    • Radar: Classical automotive radars use self-modulating FMCW radars; to get a picture of both the relative speed and distance of reflectors observed by that, you typically do a two-dimensional DFT (which really is just DFT'ing all columns of a matrix and afterwards all rows of the result).


    • Audio and Image/Video Compression: Though JPEG uses the Discrete Cosine Transform, not the DFT itself, there's ample of codecs that mechanism which at least use significant parts of a DFT.


    Note that the above list only contains things that do DFTs during operation. You can be 100% sure that during design of anything remotely related to RF, especially antenas, mixers, amplifiers, (de)modulators, a lot of Fourier Transforms / Spectral analysis was involved. Same goes for audio device design, any high-speed data link design, image analysis…



    How is it done?



    I'll just address the DFT here.



    Usually, that's implemented as an FFT, Fast Fourier Transform. That's one of the most important algorithmic discoveries of the 20th century, so I will spare but few words on it, because there's literally thousands of articles out there that explain the FFT.



    You go in and look at the $e^{j2pi frac nN k}$ multipliers of a DFT. You'll notice that these can basically be understood as ${e^{j2pi frac 1N k}}^n=W^n$; and there you have your twiddle factor. Now you avoid calculating coefficients that you've already calculated, and just swap a sign where necessary.



    That way, you can reduce the complexity of a DFT from the $N^2$ (which would be the complexity if you implemented the DFT as the naive sum) to something in the order of $Nlog N$ – a huge win, even for relatively small $N$.



    It's relatively straightforward to implement that in hardware, if you can get your whole input vector at once – you get $log N$ as a combinatorial depth and fixed coefficients at every step. The trick is knowing how (whether) to pipeline the individual layers, and how to use the specific hardware type you have (ASIC? FPGA? FPGA with hardware multipliers?). You can basically piece together $N=2^l$-length transform only from what we call Butterflies, which you'll recognize once you read about the FFT.



    In software, the principle is the same, but you need to know how to multi-thread very large transforms, and how to access memory as fast as possible by utilizing your CPU caches optimally.



    However, for both hardware and software, there's libraries that you'd just use to calculate the DFT (FFT). For Hardware, that usually comes from your FPGA vendor (e.g. Altera/Intel, Xilinx, Lattice…) , or a large ASIC design tool company (Cadence) or your ASIC house.






    share|improve this answer











    $endgroup$













    • $begingroup$
      Impressive dedication to your art, agree that 'long' is O(16) for FIR filters.
      $endgroup$
      – Neil_UK
      7 mins ago
















    6












    $begingroup$

    Devices using the Fourier Transform




    It is very difficult for an electronic device to decompose a signal in different frequencies.




    It's not.



    There's actually quite a few devices that do that, explicitly.



    First of all, you'll have to make a difference between the continuous Fourier transform (which you probably know as $mathcal Fleft{x(t)right}(f)=int_{-infty}^{infty} x(t)e^{j2pi f t},mathrm dt$) and the Digital Fourier Transform (DFT), which is what you can do with a sampled signal.



    For both, there's devices that implement these.



    Continuous Fourier Transform



    There's little in the ways of actual need for this in digital electronics – digital signals are sampled, so you'd use the DFT.



    In optics and photonics you'll notice that there's an actual chance to get perfectly periodic things for a "large" (read as: nearly as infinite as the integral above) length. Effectively, an acousto-optic element can be excited with one or multiple tones, and it will have the same correlating effects as the integral above. You don't have to look at 2018's Physics Nobel Prize winners to find an example of Fourier Optics.



    Discrete Fourier Transform



    This is really all over the place; it's such a standard processing step that as a communication engineer, we often even forget where it is.



    So, this list is far less than complete; just examples:





    • Equalizers: It's pretty easy building a digital audio equalizer with a DFT. Typically, the zero-forcing equalizer type for communication systems uses a DFT to find the frequency domain representation of the channel necessary to be "removed", inverts that and uses the IDFT to get back that back to time domain to be used as taps in a FIR filter.


    • Antenna Arrays / Beamsteering: If you have an array of antennas in fixed distance from each other, you can steer the beam of these antennas, by calculating the DFT of the "directional vector" you'd like to achieve and use the result as complex coefficients to be multiplied with the transmit signal that you distribute to these antennas. Real-world MIMO systems do that.


    • Direction Finding: What works in transmit direction works exactly the same, but reverse, in receive direction: Get a signal for each of your antennas in your array, find the complex factors between these signals, do an IDFT, get a vector containing the info how power came from which direction. Easy! And done for estimation where aircraft are, where Wifi communication partners are, submarines (though there it's not antennas but underwater microphones)…


    • Channelization: Satellites in space are expensive, so multiple TV programs need to be uplinked to one satellite. You can use a DFT (especially in an Polyphase Filterbank) to put multiple channels in one uplink, or to isolate individual channels from one wideband signal. That's not a domain of TV; it happens in audio processing, medical imaging, ultrasonic analysis, Radio broadcasting…)


    • Data Encoding for multicarrier systems: To combat the problems of wide channels (which you need if you want to transport many bits per second), namely the need for complex equalizers, you'd want to chop up your channel in many small channels (see "channelization" above). However, you can understand the DFT alone as Filterbank for frequency-shifted time-domain-rectangular filters. The nice thing about that is that these channels are very tightly packed. The other nice thing is that the convolution with the channel reduces to a point-wise multiplication which is super simple to revert. We call that method OFDM, and all Wifi, LTE, 5G, WiMax, ATSC, DVB-T, Digital Audio Broadcasting, DSL, and many more systems use that.


    • Efficient Filtering: A FIR filter is a convolution with the filter impulse response in time domain. As such, it uses a lot of operations per output sample – it's very computationally intense. You can greatly reduce that effort when you implement fast convolution, which is based on DFT'ing sections of input samples, mutliplying them with the DFT of the impulse response in frequency domain, overlapping with previous segments, and back-transformation to time domain. That's so handy that it's used in almost all systems that have long FIR filters (and "long" might start with so benign numbers as "16 taps").


    • Radar: Classical automotive radars use self-modulating FMCW radars; to get a picture of both the relative speed and distance of reflectors observed by that, you typically do a two-dimensional DFT (which really is just DFT'ing all columns of a matrix and afterwards all rows of the result).


    • Audio and Image/Video Compression: Though JPEG uses the Discrete Cosine Transform, not the DFT itself, there's ample of codecs that mechanism which at least use significant parts of a DFT.


    Note that the above list only contains things that do DFTs during operation. You can be 100% sure that during design of anything remotely related to RF, especially antenas, mixers, amplifiers, (de)modulators, a lot of Fourier Transforms / Spectral analysis was involved. Same goes for audio device design, any high-speed data link design, image analysis…



    How is it done?



    I'll just address the DFT here.



    Usually, that's implemented as an FFT, Fast Fourier Transform. That's one of the most important algorithmic discoveries of the 20th century, so I will spare but few words on it, because there's literally thousands of articles out there that explain the FFT.



    You go in and look at the $e^{j2pi frac nN k}$ multipliers of a DFT. You'll notice that these can basically be understood as ${e^{j2pi frac 1N k}}^n=W^n$; and there you have your twiddle factor. Now you avoid calculating coefficients that you've already calculated, and just swap a sign where necessary.



    That way, you can reduce the complexity of a DFT from the $N^2$ (which would be the complexity if you implemented the DFT as the naive sum) to something in the order of $Nlog N$ – a huge win, even for relatively small $N$.



    It's relatively straightforward to implement that in hardware, if you can get your whole input vector at once – you get $log N$ as a combinatorial depth and fixed coefficients at every step. The trick is knowing how (whether) to pipeline the individual layers, and how to use the specific hardware type you have (ASIC? FPGA? FPGA with hardware multipliers?). You can basically piece together $N=2^l$-length transform only from what we call Butterflies, which you'll recognize once you read about the FFT.



    In software, the principle is the same, but you need to know how to multi-thread very large transforms, and how to access memory as fast as possible by utilizing your CPU caches optimally.



    However, for both hardware and software, there's libraries that you'd just use to calculate the DFT (FFT). For Hardware, that usually comes from your FPGA vendor (e.g. Altera/Intel, Xilinx, Lattice…) , or a large ASIC design tool company (Cadence) or your ASIC house.






    share|improve this answer











    $endgroup$













    • $begingroup$
      Impressive dedication to your art, agree that 'long' is O(16) for FIR filters.
      $endgroup$
      – Neil_UK
      7 mins ago














    6












    6








    6





    $begingroup$

    Devices using the Fourier Transform




    It is very difficult for an electronic device to decompose a signal in different frequencies.




    It's not.



    There's actually quite a few devices that do that, explicitly.



    First of all, you'll have to make a difference between the continuous Fourier transform (which you probably know as $mathcal Fleft{x(t)right}(f)=int_{-infty}^{infty} x(t)e^{j2pi f t},mathrm dt$) and the Digital Fourier Transform (DFT), which is what you can do with a sampled signal.



    For both, there's devices that implement these.



    Continuous Fourier Transform



    There's little in the ways of actual need for this in digital electronics – digital signals are sampled, so you'd use the DFT.



    In optics and photonics you'll notice that there's an actual chance to get perfectly periodic things for a "large" (read as: nearly as infinite as the integral above) length. Effectively, an acousto-optic element can be excited with one or multiple tones, and it will have the same correlating effects as the integral above. You don't have to look at 2018's Physics Nobel Prize winners to find an example of Fourier Optics.



    Discrete Fourier Transform



    This is really all over the place; it's such a standard processing step that as a communication engineer, we often even forget where it is.



    So, this list is far less than complete; just examples:





    • Equalizers: It's pretty easy building a digital audio equalizer with a DFT. Typically, the zero-forcing equalizer type for communication systems uses a DFT to find the frequency domain representation of the channel necessary to be "removed", inverts that and uses the IDFT to get back that back to time domain to be used as taps in a FIR filter.


    • Antenna Arrays / Beamsteering: If you have an array of antennas in fixed distance from each other, you can steer the beam of these antennas, by calculating the DFT of the "directional vector" you'd like to achieve and use the result as complex coefficients to be multiplied with the transmit signal that you distribute to these antennas. Real-world MIMO systems do that.


    • Direction Finding: What works in transmit direction works exactly the same, but reverse, in receive direction: Get a signal for each of your antennas in your array, find the complex factors between these signals, do an IDFT, get a vector containing the info how power came from which direction. Easy! And done for estimation where aircraft are, where Wifi communication partners are, submarines (though there it's not antennas but underwater microphones)…


    • Channelization: Satellites in space are expensive, so multiple TV programs need to be uplinked to one satellite. You can use a DFT (especially in an Polyphase Filterbank) to put multiple channels in one uplink, or to isolate individual channels from one wideband signal. That's not a domain of TV; it happens in audio processing, medical imaging, ultrasonic analysis, Radio broadcasting…)


    • Data Encoding for multicarrier systems: To combat the problems of wide channels (which you need if you want to transport many bits per second), namely the need for complex equalizers, you'd want to chop up your channel in many small channels (see "channelization" above). However, you can understand the DFT alone as Filterbank for frequency-shifted time-domain-rectangular filters. The nice thing about that is that these channels are very tightly packed. The other nice thing is that the convolution with the channel reduces to a point-wise multiplication which is super simple to revert. We call that method OFDM, and all Wifi, LTE, 5G, WiMax, ATSC, DVB-T, Digital Audio Broadcasting, DSL, and many more systems use that.


    • Efficient Filtering: A FIR filter is a convolution with the filter impulse response in time domain. As such, it uses a lot of operations per output sample – it's very computationally intense. You can greatly reduce that effort when you implement fast convolution, which is based on DFT'ing sections of input samples, mutliplying them with the DFT of the impulse response in frequency domain, overlapping with previous segments, and back-transformation to time domain. That's so handy that it's used in almost all systems that have long FIR filters (and "long" might start with so benign numbers as "16 taps").


    • Radar: Classical automotive radars use self-modulating FMCW radars; to get a picture of both the relative speed and distance of reflectors observed by that, you typically do a two-dimensional DFT (which really is just DFT'ing all columns of a matrix and afterwards all rows of the result).


    • Audio and Image/Video Compression: Though JPEG uses the Discrete Cosine Transform, not the DFT itself, there's ample of codecs that mechanism which at least use significant parts of a DFT.


    Note that the above list only contains things that do DFTs during operation. You can be 100% sure that during design of anything remotely related to RF, especially antenas, mixers, amplifiers, (de)modulators, a lot of Fourier Transforms / Spectral analysis was involved. Same goes for audio device design, any high-speed data link design, image analysis…



    How is it done?



    I'll just address the DFT here.



    Usually, that's implemented as an FFT, Fast Fourier Transform. That's one of the most important algorithmic discoveries of the 20th century, so I will spare but few words on it, because there's literally thousands of articles out there that explain the FFT.



    You go in and look at the $e^{j2pi frac nN k}$ multipliers of a DFT. You'll notice that these can basically be understood as ${e^{j2pi frac 1N k}}^n=W^n$; and there you have your twiddle factor. Now you avoid calculating coefficients that you've already calculated, and just swap a sign where necessary.



    That way, you can reduce the complexity of a DFT from the $N^2$ (which would be the complexity if you implemented the DFT as the naive sum) to something in the order of $Nlog N$ – a huge win, even for relatively small $N$.



    It's relatively straightforward to implement that in hardware, if you can get your whole input vector at once – you get $log N$ as a combinatorial depth and fixed coefficients at every step. The trick is knowing how (whether) to pipeline the individual layers, and how to use the specific hardware type you have (ASIC? FPGA? FPGA with hardware multipliers?). You can basically piece together $N=2^l$-length transform only from what we call Butterflies, which you'll recognize once you read about the FFT.



    In software, the principle is the same, but you need to know how to multi-thread very large transforms, and how to access memory as fast as possible by utilizing your CPU caches optimally.



    However, for both hardware and software, there's libraries that you'd just use to calculate the DFT (FFT). For Hardware, that usually comes from your FPGA vendor (e.g. Altera/Intel, Xilinx, Lattice…) , or a large ASIC design tool company (Cadence) or your ASIC house.






    share|improve this answer











    $endgroup$



    Devices using the Fourier Transform




    It is very difficult for an electronic device to decompose a signal in different frequencies.




    It's not.



    There's actually quite a few devices that do that, explicitly.



    First of all, you'll have to make a difference between the continuous Fourier transform (which you probably know as $mathcal Fleft{x(t)right}(f)=int_{-infty}^{infty} x(t)e^{j2pi f t},mathrm dt$) and the Digital Fourier Transform (DFT), which is what you can do with a sampled signal.



    For both, there's devices that implement these.



    Continuous Fourier Transform



    There's little in the ways of actual need for this in digital electronics – digital signals are sampled, so you'd use the DFT.



    In optics and photonics you'll notice that there's an actual chance to get perfectly periodic things for a "large" (read as: nearly as infinite as the integral above) length. Effectively, an acousto-optic element can be excited with one or multiple tones, and it will have the same correlating effects as the integral above. You don't have to look at 2018's Physics Nobel Prize winners to find an example of Fourier Optics.



    Discrete Fourier Transform



    This is really all over the place; it's such a standard processing step that as a communication engineer, we often even forget where it is.



    So, this list is far less than complete; just examples:





    • Equalizers: It's pretty easy building a digital audio equalizer with a DFT. Typically, the zero-forcing equalizer type for communication systems uses a DFT to find the frequency domain representation of the channel necessary to be "removed", inverts that and uses the IDFT to get back that back to time domain to be used as taps in a FIR filter.


    • Antenna Arrays / Beamsteering: If you have an array of antennas in fixed distance from each other, you can steer the beam of these antennas, by calculating the DFT of the "directional vector" you'd like to achieve and use the result as complex coefficients to be multiplied with the transmit signal that you distribute to these antennas. Real-world MIMO systems do that.


    • Direction Finding: What works in transmit direction works exactly the same, but reverse, in receive direction: Get a signal for each of your antennas in your array, find the complex factors between these signals, do an IDFT, get a vector containing the info how power came from which direction. Easy! And done for estimation where aircraft are, where Wifi communication partners are, submarines (though there it's not antennas but underwater microphones)…


    • Channelization: Satellites in space are expensive, so multiple TV programs need to be uplinked to one satellite. You can use a DFT (especially in an Polyphase Filterbank) to put multiple channels in one uplink, or to isolate individual channels from one wideband signal. That's not a domain of TV; it happens in audio processing, medical imaging, ultrasonic analysis, Radio broadcasting…)


    • Data Encoding for multicarrier systems: To combat the problems of wide channels (which you need if you want to transport many bits per second), namely the need for complex equalizers, you'd want to chop up your channel in many small channels (see "channelization" above). However, you can understand the DFT alone as Filterbank for frequency-shifted time-domain-rectangular filters. The nice thing about that is that these channels are very tightly packed. The other nice thing is that the convolution with the channel reduces to a point-wise multiplication which is super simple to revert. We call that method OFDM, and all Wifi, LTE, 5G, WiMax, ATSC, DVB-T, Digital Audio Broadcasting, DSL, and many more systems use that.


    • Efficient Filtering: A FIR filter is a convolution with the filter impulse response in time domain. As such, it uses a lot of operations per output sample – it's very computationally intense. You can greatly reduce that effort when you implement fast convolution, which is based on DFT'ing sections of input samples, mutliplying them with the DFT of the impulse response in frequency domain, overlapping with previous segments, and back-transformation to time domain. That's so handy that it's used in almost all systems that have long FIR filters (and "long" might start with so benign numbers as "16 taps").


    • Radar: Classical automotive radars use self-modulating FMCW radars; to get a picture of both the relative speed and distance of reflectors observed by that, you typically do a two-dimensional DFT (which really is just DFT'ing all columns of a matrix and afterwards all rows of the result).


    • Audio and Image/Video Compression: Though JPEG uses the Discrete Cosine Transform, not the DFT itself, there's ample of codecs that mechanism which at least use significant parts of a DFT.


    Note that the above list only contains things that do DFTs during operation. You can be 100% sure that during design of anything remotely related to RF, especially antenas, mixers, amplifiers, (de)modulators, a lot of Fourier Transforms / Spectral analysis was involved. Same goes for audio device design, any high-speed data link design, image analysis…



    How is it done?



    I'll just address the DFT here.



    Usually, that's implemented as an FFT, Fast Fourier Transform. That's one of the most important algorithmic discoveries of the 20th century, so I will spare but few words on it, because there's literally thousands of articles out there that explain the FFT.



    You go in and look at the $e^{j2pi frac nN k}$ multipliers of a DFT. You'll notice that these can basically be understood as ${e^{j2pi frac 1N k}}^n=W^n$; and there you have your twiddle factor. Now you avoid calculating coefficients that you've already calculated, and just swap a sign where necessary.



    That way, you can reduce the complexity of a DFT from the $N^2$ (which would be the complexity if you implemented the DFT as the naive sum) to something in the order of $Nlog N$ – a huge win, even for relatively small $N$.



    It's relatively straightforward to implement that in hardware, if you can get your whole input vector at once – you get $log N$ as a combinatorial depth and fixed coefficients at every step. The trick is knowing how (whether) to pipeline the individual layers, and how to use the specific hardware type you have (ASIC? FPGA? FPGA with hardware multipliers?). You can basically piece together $N=2^l$-length transform only from what we call Butterflies, which you'll recognize once you read about the FFT.



    In software, the principle is the same, but you need to know how to multi-thread very large transforms, and how to access memory as fast as possible by utilizing your CPU caches optimally.



    However, for both hardware and software, there's libraries that you'd just use to calculate the DFT (FFT). For Hardware, that usually comes from your FPGA vendor (e.g. Altera/Intel, Xilinx, Lattice…) , or a large ASIC design tool company (Cadence) or your ASIC house.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited 1 hour ago

























    answered 1 hour ago









    Marcus MüllerMarcus Müller

    34.1k36199




    34.1k36199












    • $begingroup$
      Impressive dedication to your art, agree that 'long' is O(16) for FIR filters.
      $endgroup$
      – Neil_UK
      7 mins ago


















    • $begingroup$
      Impressive dedication to your art, agree that 'long' is O(16) for FIR filters.
      $endgroup$
      – Neil_UK
      7 mins ago
















    $begingroup$
    Impressive dedication to your art, agree that 'long' is O(16) for FIR filters.
    $endgroup$
    – Neil_UK
    7 mins ago




    $begingroup$
    Impressive dedication to your art, agree that 'long' is O(16) for FIR filters.
    $endgroup$
    – Neil_UK
    7 mins ago













    0












    $begingroup$

    That's basically what a spectrum analyzer does:



    https://www.electronics-notes.com/articles/test-methods/spectrum-analyzer/realtime-spectrum-analyser.php






    share|improve this answer









    $endgroup$









    • 2




      $begingroup$
      No it's not what a spectrum analyzer does in general. Some (many) spectrum analyzers have an FFT mode, but even then, what the spectrum analyzer shows you is a PSD estimate, not a Fourier transform.
      $endgroup$
      – Marcus Müller
      2 hours ago
















    0












    $begingroup$

    That's basically what a spectrum analyzer does:



    https://www.electronics-notes.com/articles/test-methods/spectrum-analyzer/realtime-spectrum-analyser.php






    share|improve this answer









    $endgroup$









    • 2




      $begingroup$
      No it's not what a spectrum analyzer does in general. Some (many) spectrum analyzers have an FFT mode, but even then, what the spectrum analyzer shows you is a PSD estimate, not a Fourier transform.
      $endgroup$
      – Marcus Müller
      2 hours ago














    0












    0








    0





    $begingroup$

    That's basically what a spectrum analyzer does:



    https://www.electronics-notes.com/articles/test-methods/spectrum-analyzer/realtime-spectrum-analyser.php






    share|improve this answer









    $endgroup$



    That's basically what a spectrum analyzer does:



    https://www.electronics-notes.com/articles/test-methods/spectrum-analyzer/realtime-spectrum-analyser.php







    share|improve this answer












    share|improve this answer



    share|improve this answer










    answered 3 hours ago









    KitKit

    21428




    21428








    • 2




      $begingroup$
      No it's not what a spectrum analyzer does in general. Some (many) spectrum analyzers have an FFT mode, but even then, what the spectrum analyzer shows you is a PSD estimate, not a Fourier transform.
      $endgroup$
      – Marcus Müller
      2 hours ago














    • 2




      $begingroup$
      No it's not what a spectrum analyzer does in general. Some (many) spectrum analyzers have an FFT mode, but even then, what the spectrum analyzer shows you is a PSD estimate, not a Fourier transform.
      $endgroup$
      – Marcus Müller
      2 hours ago








    2




    2




    $begingroup$
    No it's not what a spectrum analyzer does in general. Some (many) spectrum analyzers have an FFT mode, but even then, what the spectrum analyzer shows you is a PSD estimate, not a Fourier transform.
    $endgroup$
    – Marcus Müller
    2 hours ago




    $begingroup$
    No it's not what a spectrum analyzer does in general. Some (many) spectrum analyzers have an FFT mode, but even then, what the spectrum analyzer shows you is a PSD estimate, not a Fourier transform.
    $endgroup$
    – Marcus Müller
    2 hours ago











    0












    $begingroup$

    You can't get much more "bare metal" and "hardware" than a set of vibrating reeds.



    http://www.stichtco.com/freq_met.htm



    So what hardware does a fourier transform, a bunch of resonant systems can do that






    share|improve this answer









    $endgroup$


















      0












      $begingroup$

      You can't get much more "bare metal" and "hardware" than a set of vibrating reeds.



      http://www.stichtco.com/freq_met.htm



      So what hardware does a fourier transform, a bunch of resonant systems can do that






      share|improve this answer









      $endgroup$
















        0












        0








        0





        $begingroup$

        You can't get much more "bare metal" and "hardware" than a set of vibrating reeds.



        http://www.stichtco.com/freq_met.htm



        So what hardware does a fourier transform, a bunch of resonant systems can do that






        share|improve this answer









        $endgroup$



        You can't get much more "bare metal" and "hardware" than a set of vibrating reeds.



        http://www.stichtco.com/freq_met.htm



        So what hardware does a fourier transform, a bunch of resonant systems can do that







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered 37 mins ago









        JasenJasen

        11k1530




        11k1530






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Electrical Engineering Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2felectronics.stackexchange.com%2fquestions%2f425008%2fwhat-kind-of-hardware-implements-fourier-transform%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            “%fieldName is a required field.”, in Magento2 REST API Call for GET Method Type The Next...

            How to change City field to a dropdown in Checkout step Magento 2Magento 2 : How to change UI field(s)...

            夢乃愛華...