Most Important Algorithm That Averted a Nuclear Conflict
After the end of the Second World War in 1945, entire world saw the power of nuclear weapons detonated at Hiroshima and Nagasaki. The United States, the Soviet Union, and the United Kingdom signed the Nuclear Test-Ban Treaty in Moscow on August 5, 1963, banning nuclear weapons tests in the atmosphere, outer space, and underwater. However, underground tests were not banned, which began the race to develop a method to detect underground nuclear tests.
In October 1963, the United States initiated the Vela Uniform program to develop a method to detect underground nuclear detonations. The task was to distinguish underground detonations from other seismic activities. Seven underground nuclear detonations were made in the continental United States and Alaska from October 1963 to July 1971. The scientists analyzed seismic traces from different parts to find the location of the detonation site. An algorithm known as the Fast Fourier Transform (FFT) has been developed to effectively distinguish seismic events from underground nuclear tests. The development of FFT played a significant role in the Cold War by reducing further nuclear detonations and helping in the development of the United States’ missile defense system.
The history of the Fast Fourier Transform (FFT) dates back to 1805, when Carl Friedrich Gauss introduced it in Latin while attempting to compute asteroid orbits. This algorithm remained obscure for 160 years until 1965, when James Cooley and John Tukey independently rediscovered and popularized it.
The Fast Fourier Transform is an algorithm that converts a time-domain signal into its frequency-domain representation. In simpler terms, it’s a mathematical technique that takes a signal, such as an audio waveform or a seismic data recording, and decomposes it into its constituent frequencies, revealing the constituent frequencies combined to form the domain signal.
FFT assumes the signal is discrete, unlike the Fourier transform (FT), which takes a continuous signal as input. The discrete Fourier transform (DFT) algorithm also assumes the signals are discrete for the conversion in the frequency domain, but it is slower than FFT, especially when the size of the domain signal is large. The time complexity of DFT is O(N²). FFT computes the DFT and its inverse with a time complexity of O(Nlog₂N), significantly reducing the calculations needed for conversion. A time domain signal can be converted into a frequency domain signal through FFT via the following formula:
Now let’s see the FFT in action …
Let’s create a signal by adding two sinusoidal signals with different frequencies:
N = 500
T = 1.0 / 800.0
x = np.linspace(0.0, N*T, N, endpoint=False)
y1= 0.8*np.sin(5.0 * 2.0*np.pi*x) #signal 1
y2 = 0.4*np.sin(15.0 * 2.0*np.pi*x) #signal 2
y = y1+y2
plt.figure(figsize=(10,5))
plt.title("Time Domain")
plt.plot(x,y, label='Final signal')
plt.xlabel("Time")
plt.ylabel("Amplitude")
plt.grid()
plt.legend()
To find out what frequencies were used to create the above signal, we can transform the signal from time domain to frequency domain using FFT.
yf = fft(y)
xf = fftfreq(N, T)[:N//2]
plt.figure(figsize=(10,5))
plt.title("Frequency Domain")
plt.stem(xf, 2.0/N * np.abs(yf[0:N//2]))
plt.xlabel("Frequency")
plt.ylabel("Amplitude")
plt.xticks(np.arange(0, 70, 5))
plt.xlim([0, 70])
plt.grid()
Looking at the frequency domain, the peak values tell us what frequencies were used. Their are two peaks present in the frequency domain at 5 Hz and 15 Hz, and the amplitude in the frequency domain can tell how much of that frequency is present in the final signal. Below is the final signal along with it’s constituent signals.
In audio production, unwanted tunes are removed from the music track by damping the frequencies in the frequency domain. The FFT analysis of machine-generated noise is used to identify potential issues, such as loose screws, which produce distinct frequencies that can be observed in the frequency domain.
FFT in Image Processing
FFT is widely used in the domains of image filtering, image processing, and image compression. Let’s look at some of the basic image filters.
For simplicity, we will use the following grayscale image:
After taking the FFT of the image, we get the phase and amplitude shown below.
We will look only at the amplitude and not the phase of the image.
High Pass Filter:
A high-pass filter only allows higher frequencies to pass through and blocks all the lower frequencies. It enhances the high-frequency components of an image while suppressing the low-frequency parts. This helps in sharpening edges, emphasizing fine details, or reducing low-frequency noise.
Let’s apply a high-pass filter to the image.
Low Pass Filter:
A low-pass filter blocks higher frequencies and allows lower frequencies to pass through. This filtering technique helps in smoothing or blurring the image, reducing noise, and preserving the overall structure.
Let’s apply a low-pass filter to the image.
A low-pass filter can also be used for image compression if sufficient frequencies are allowed to pass through. Here is an example:
The compressed image in the middle is formed by applying a low-pass filter to the original image. Looking at the differences in both pictures, we cannot tell any differences; hence, not all of the frequencies are needed to preserve the image.
The Fast Fourier Transform (FFT) is a vital mathematical technique with wide-ranging importance. It enables the analysis of signals, images, and data in the frequency domain, playing a critical role in fields such as signal processing, image enhancement, image filtering,data compression, medical imaging, cryptography, and scientific research. Its versatility and ability to unveil underlying frequency information make it an indispensable tool in diverse applications across various domains.
