mathematical signal pattern transforms such as FFT

see also:

• History of Mathematics
• a brief summary of mathematical principles and tools
• a brief summary of number theory
• mensuration - how to measure area, volume, etc of various shapes
• Algebra
• geometry
• matrices
• Calculus
• Circular functions
• Coordinate geometry, parabolae, etc
• Finance equations
• Logarithmic, exponential and hyperbolic functions
• Probability theory
• a brief summary of statistics principles and tools

• see also:
  • oscilloscopes
  • https://www.youtube.com/watch?v=spUNpyF58BY 3Blue1Brown's Youtube explanation
• Discrete Fourier Transform (DFT) allows us to transform a signal or pattern in the time domain into the frequency domain by ascertaining the various sinusoid frequencies and their characteristics which make up the time domain signal
• DFT was invented in 1805 by Fourier (although Gauss probably also discovered it whilst trying to work out harmonics of asteroids but was never published in a way others could understand it)
• the FFT was invented to try to discover if another nation was doing underground nuclear tests from seismic data, as unfortunately for DFT, if you had a million sample points, doing DFT would require a million x million calculations which would take a 1960s computer 3 years. In 1960's, Tukey invented the FFT while Cooley created the computer programming (published their paper in 1965) to achieve this which could reduce this million sample transform by 50,000x to 35 minutes.
• FFT has become the basics for most compression and signal processing algorithms

• for N samples with a time or space domain signal s(n) value, the DFT value S(k) at any frequency k is calculated as:

S(k) = sum from n=0 to n=N-1 ( s(n) x e^−j2πk/N )

• j = sqrt(-1) ie. complex number and remember eⁱⁿ = cos(n) + isin(n)
• NB.
  • the s(n0) x e^−j2πk/N component essentially winds the signal amplitude around a point on a complex number plot (see https://www.youtube.com/watch?v=spUNpyF58BY at ~14min)
  • what we want to determine is the “centre of mass” of the sampled points when plotted on this complex number chart hence all these are essentially a scaled up average for a given frequency
• k = 1 = frequency of the length of the sampling time period; k= 2 is half this frequency and so on; NB. K=0 value gives the DC offset.
• thus you iterate through for each value of k from 0 to N and ascertain S(k) by adding up all the sample values which result from using this equation
• the frequency in hertz = k / length of time signal = k x sampling frequency / number of samples N
• the bin width can be calculated by using k = 1 thus bin width = sampling frequency / N
• to get a narrower bin width (more resolution), can just use a longer period of data or a faster sampling frequency
• if the signal frequency is larger than the time period, we will get erroneous results due to spectral leakage into other frequency bins not included in our calculations

• it is calculated by efficiently decomposing a signal into its sinusoidal frequency components using a divide-and-conquer approach to ignore needing to calculate data for points which could be predicted from the symmetric nature of how sine waves and cosine waves overlap at different frequencies and that reduces computation time for the Discrete Fourier Transform (DFT) from O(N²) to Fast Fourier Transform (FFT) O(Nlog⁡N), and the larger N is the greater that compute savings
• the FFT algorithm recursively splits the input data (of length N, often a power of 2) into even- and odd-indexed elements.
• it computes two half-length DFTs (one for the even-indexed data, one for the odd)
• these half-length transforms are combined using complex exponential “twiddle factors” e^−j2πk/N to produce the full DFT
• the recombination is performed using “butterfly” operations, which involve one complex multiplication and two complex additions for each operation
• this process continues recursively until all subproblems are of length 1, at which point the DFT is trivial
• the classic FFT (Cooley-Tukey algorithm) works best when N is a power of 2.
  • total operations are reduced from N² (direct DFT where you need to calculate N samples for N frequencies) to Nlog⁡2N (FFT)
• see https://www.youtube.com/watch?v=h7apO7q16V0 for a polynomial / matrices approach to FFT
• when taking absolute values to get magnitude and essentially ignoring phase details, a two-sided FFT gives positive frequencies on the left and negative frequencies on the right separated by the Nyquist frequency in the middle - the Nyquist Sampling Theorem which states we can only know sampling information up to half the sampling rate. A One-Sided FFT only shows the Positive frequencies. ¹⁾
• how you then manipulate or analyze the FFT output will depend on why you need to
  • we mainly just need the relative Y values to get a picture of the dominant frequencies (eg. is there 60Hz AC noise in the signal), whereas the actual Y value is mainly used in power equations
  • if you want the actual amplitude from a One-Sided FFT then Amplitude = 2 x DFT(k) value /number of samples (excluding 0 and Nyquist frequencies)

• One-sided Power Spectrum from a One-Sided FFT:
  • as Power of a sinusoid = Amplitude²/2 = (DFT(k)*2)²/2N² = 2xDFT(k)²/N² (excluding 0 and Nyquist frequencies)
  • this is only valid if:
    • we are using a rectangular window and not a Blackman or hamming windows (these have attenuations on either side so lower the average amplitudes), and,
    • time period is stationary (signal is constant across the time period and not just a short event or a gradually changing one), and,
    • the time signals produce discrete frequency power spectra and not a continuous spectrum
  • to convert power into dB, dB = 10 x log₁₀(Power / Reference Power), Reference Power may = 1W or 1 mW depending upon the situation
    • NB. to convert amplitude or voltage into dB, those ratios must first be squared so power dB = 20 x log₁₀(Amplitude / Reference Amplitude)
  • to convert dB back to Watts, Power = Reference Power x 10 ^(dB/10)
    • eg. if 0dB = 1mW (the reference power) then this dB is called “dBm” and thus Power in W = 0.001W x 10^(dBm/10) = 10^(dBm/10)/1000
• Power Spectral Density curve
  • as frequencies get closer together, the power will merge creating a smoother curve representing the power density of the region rather than reflecting just the power of one frequency
  • the wider the window (bandwidth), the narrower the power density curve becomes
  • the Power Spectral Density = Power Spectrum / Equivalent Noise Bandwidth = DFT(k)²/(sample rate x N)
    • where Power Spectrum = DFT(k)²/N²
    • and Equivalent Noise Bandwidth = sample rate / N ²⁾
  • this is the display one gets on SDR radio software which is displaying the dB power strength of each radio frequency

• a technique that exposes the strengths of the sinusoid frequencies and the exponentials that make up a pattern
• indeed it is just the Fourier transform multiplied by an exponential term
• the output imaginary term gives us the coefficient or angular frequency of the sinusoidal
• the output real term gives us the coefficient of the exponential term
• it is also used to turn calculus into algebra:
  • https://www.youtube.com/watch?v=n2y7n6jw5d0
• see https://en.wikipedia.org/wiki/Laplace_transform