The Most Important Algorithm Of All Time

0:00 This is a video about the most important algorithm of all time,

0:04 the Fast Fourier Transform or FFT.

0:07 I mean, you use it all the time

0:09 including right now to watch this video

0:11 and it's used in radar and sonar, 5G and WiFi.

0:15 Basically, anytime a signal is processed,

0:17 there's a good chance that a Fast Fourier Transform

0:20 is involved.

0:21 But on top of all this, the FFT was discovered by scientists

0:25 trying to detect covert nuclear weapons tests.

0:28 And if they had discovered it sooner,

0:30 it may have put a stop to the nuclear arms race.

0:36 You know I always assumed that the nuclear arms race

0:39 was inevitable, that once the U.S. dropped atomic bombs

0:41 on Hiroshima and Nagasaki,

0:43 it was just unavoidable that all the other major powers

0:45 would develop nukes.

0:47 But maybe it wasn't because it was clear to everyone

0:51 that nuclear weapons were game changing.

0:54 The bomb dropped on Hiroshima released a thousand times

0:56 more energy than the biggest conventional explosive

0:59 so other countries were rightfully concerned.

1:03 At the end of the war, Canada and the U.K.

1:05 requested a meeting to discuss what would be done

1:08 about nuclear weapons.

1:09 And contrary to what I expected,

1:12 the U.S. was actually open to these discussions.

1:15 They realized that they wouldn't be the only nation

1:18 with nukes for long.

1:19 So they offered to decommission all their nuclear weapons

1:22 if other nations would pledge never to make them.

1:28 This was known as the Baruch plan

1:31 and it proposed that an international body would control

1:34 all radioactive materials on earth,

1:36 from mining to refining to using these materials

1:39 for peaceful purposes as a nuclear power generation.

1:43 But the Soviets rejected the proposal.

1:45 They saw it as just another ploy to maintain

1:48 American nuclear dominance

1:49 and so the global nuclear arms race began.

1:55 To develop new nuclear weapons required extensive testing

1:59 and most of it was done in remote places like the Arctic

2:02 or the South Pacific Islands.

2:04 The U.S. also created a nuclear testing site in Nevada,

2:07 the radioactive products of which blew across the country

2:10 so that outside of Japan, the people most adversely affected

2:14 by American nuclear weapons were Americans themselves.

2:18 The U.S. soon graduated from fission weapons

2:21 to thermonuclear bombs which combined fission and fusion

2:24 to release even more energy.

2:28 They were as big leap from the first atomic bombs

2:31 as those devices were from conventional explosives,

2:34 a thousand times again more powerful.

2:37 - Annihilation of any life on earth has being brought

2:41 within the range of technical possibility.

2:48 - In 1954 at Bikini Atoll in the South Pacific,

2:51 the U.S. tested a new thermonuclear design

2:54 that used lithium deuteride as a fuel

2:56 and they expected the device code named Shrimp

2:58 to release the energy equivalent of six million tons of TNT

3:03 but they were wrong.

3:04 (bomb blasts)

3:09 It released two and a half times that

3:11 due to unanticipated reactions with lithium-7.

3:15 And as a result, more radioactive material was created

3:18 and it rained down over a much larger area than planned.

3:22 Residents of neighboring atolls were only evacuated

3:24 three days later suffering from radiation sickness.

3:28 And further east, the 23 crew of a Japanese fishing boat

3:31 were caught in a flurry of radioactive white ash.

3:34 And by that evening,

3:35 they were suffering from acute radiation syndrome.

3:39 One of the crew died from ensuing complications

3:41 six months later.

3:42 - As a result of the extended illness

3:44 brought about by his exposure to the radiation fallout.

3:48 - These events triggered public outcry

3:51 against nuclear testing.

3:52 The modern peace sign was designed in the 1950s

3:55 by combining the semaphore letters for N and D

3:59 standing for nuclear disarmament.

4:01 A number of world leaders called for a comprehensive

4:04 test ban, no more testing of nuclear weapons by any state

4:09 and this call was actually taken seriously

4:11 by the world's nuclear powers.

4:13 They entered into negotiations at meetings

4:15 with very literal names like

4:17 the Conference on the Discontinuance of Nuclear Weapon Tests

4:20 held in Geneva in 1958.

4:24 And to show just how serious they were,

4:26 they even stopped all testing during the negotiations

4:29 which is why 1959 is the only year in a long stretch

4:33 when no nuclear weapons were detonated.

4:36 But there was a big problem with negotiating

4:39 a comprehensive test ban which is how do you know

4:42 that the other side will hold up their end of the bargain?

4:46 The U.S. worried that the Soviets would continue

4:48 testing covertly and leapfrog them technologically

4:51 and the Soviets similarly distrusted the U.S..

4:55 So to address these concerns,

4:56 they convened the Conference of Experts to Study

4:59 the Possibility of Detecting Violations

5:02 of a Possible Agreement on Suspension of Nuclear Tests.

5:06 Seriously, that was the name, I am not making this up.

5:13 Now detecting atmospheric tests was fairly straightforward.

5:16 The radioactive isotopes they produced disperse

5:19 in the atmosphere and can be detected

5:21 thousands of kilometers away.

5:23 Underwater tests produce distinctive sounds

5:26 that travel efficiently around a kilometer below the surface

5:29 of the ocean and these can be picked up by hydrophones.

5:33 But underground tests are much harder to detect from afar

5:37 because their radiation is mostly contained

5:40 and the Soviets refused to allow onsite compliance visits

5:43 which they regarded as espionage.

5:46 And this is ultimately why when a test ban treaty was signed

5:49 in 1963, it was only a partial ban.

5:53 It banned testing underwater,

5:55 in the atmosphere and in space,

5:57 places where compliance could be verified,

5:59 but it didn't ban testing underground for the simple reason

6:03 that it was almost impossible to verify compliance.

6:06 But scientists had been trying to find a way

6:08 to reliably detect underground detonations.

6:11 Following the Geneva meeting, American and Soviet scientists

6:14 formed a working group to discuss the issue

6:17 and their idea was to use seismometers located

6:20 outside the countries where nukes were being tested

6:22 to detect the faint ground vibrations caused by explosions.

6:27 The problem was how do you distinguish a nuclear test

6:30 from an earthquake?

6:32 Every day around the world,

6:33 there are close to 300 earthquakes

6:35 with a magnitude of three or greater.

6:39 In addition, part of the purpose of detecting

6:41 your adversaries tests is to spy on them,

6:44 to know how big of an explosion they can make.

6:47 But the seismometer signal depends not only on the yield

6:50 of the device but also on how deep it was buried.

6:54 For a given yield, deeper explosions appear smaller.

6:58 So scientists wanted a method to reliably determine

7:01 whether a given signal was a bomb or an earthquake

7:04 and if it was a bomb, how big it was

7:06 and how deep it was buried.

7:09 They knew that all this information was contained

7:11 in the seismometer signal but it couldn't just be read off

7:15 by looking at the squiggles.

7:16 They needed to know how much of different frequencies

7:19 were present which meant they needed to take

7:22 a Fourier transform.

7:25 A Fourier transform is a way of decomposing a signal

7:28 into pure sine waves, each with its own amplitude

7:32 and frequency that add to make it up.

7:35 This seems a bit like magic since the sum

7:38 of a set of sine waves can look arbitrarily complicated

7:40 and nothing like its component parts.

7:44 There are some elegant ways to understand

7:46 how Fourier transforms work,

7:47 shout out to the awesome video by 3Blue1Brown.

7:50 But I wanna take more of a brute force approach.

7:53 If you wanna know how much of a particular sine wave

7:56 is in a signal, just multiply the signal by the sine wave

8:00 at each point and then add up the area under the curve.

8:05 As a simple example, say our signal is just a sine wave

8:08 with a certain frequency but pretend we don't know that

8:11 and we're trying to figure out

8:12 which sine waves add to make it up.

8:15 Well, if you multiply this signal by a sine wave

8:17 of an arbitrary frequency, the two waves are uncorrelated.

8:22 You're just as likely to find places where they have

8:23 the same sign, both positive or both negative

8:26 as where they have opposite signs and therefore

8:29 when you multiply them together, the area above the x-axis

8:32 is equal to the area below the x-axis.

8:35 So these areas add up to zero which means

8:38 that frequency sine wave is not a part of your signal

8:42 and this will be true for almost all frequencies

8:45 you could try assuming you're looking over

8:46 a long enough timeframe.

8:48 The only exception is if the frequency of the sine wave

8:51 exactly matches that of the signal,

8:55 now these waves are correlated

8:57 so their product is always positive and so is the area

9:01 under the curve that indicates

9:02 that this sine wave is part of our signal.

9:06 And this trick works even if the signal is composed

9:08 of a bunch of different frequencies.

9:10 If the sine waves frequency is one of the components

9:13 of the signal it will correlate with the signal

9:15 producing a non-zero area.

9:17 And the size of this area tells you the relative amplitude

9:20 of that frequency sine wave in the signal.

9:24 Repeat this process for all frequencies of sine waves

9:27 and you get the frequency spectrum.

9:29 Essentially which frequencies are present

9:31 and in what proportions.

9:35 Now so far I've only talked about sine waves

9:38 but if the signal is a cosine wave,

9:40 then even if you multiply it by a sine wave

9:42 of the exact same frequency,

9:44 the area under the curve will be zero.

9:47 So for each frequency,

9:48 we actually need to multiply by a sine wave

9:51 and a cosine wave and find the amplitudes for each.

9:55 The ratio of these amplitudes indicates the phase

9:58 of the signal that is how much it's shifted

10:01 to the left or to the right.

10:03 You can calculate these sine and cosine amplitudes

10:05 separately or you can use Euler's formula

10:09 so you only need to multiply your signal

10:11 by one exponential term.

10:13 Then the real part of the sum is the cosine amplitude

10:16 and the imaginary part is the sine amplitude.

10:20 In the American delegation at the Geneva meeting,

10:22 there was a physicist, Richard Garwin

10:24 and a mathematician John Tukey.

10:27 They got into a debate with the Soviet delegation

10:29 over which nation's seismometers were superior.

10:32 So Garwin simulated the responses of both countries' devices

10:36 on a computer at CERN.

10:39 The next day, everyone agreed there wasn't much difference.

10:43 The real obstacle to detecting underground explosions

10:46 wasn't the accuracy of the seismometers,

10:49 it was the vast amounts of computation required

10:51 to Fourier transform the seismometer signals.

10:56 Here's an example seismometer signal

10:58 and its Fourier transform.

11:00 Thus far I've been thinking about signals

11:02 as infinite continuous waves

11:04 and when you take their Fourier transform,

11:06 you get an infinite continuous frequency spectrum.

11:09 But real world signals are not like that.

11:12 They are finite and made up of individual samples

11:14 or data points.

11:16 Even though a seismometer signal looks smooth

11:19 and continuous, it doesn't record ground motion

11:22 with infinite precision.

11:24 There is some fundamental graininess to the data

11:27 so what you have is discreet finite data.

11:30 So you can't use the idealized Fourier transform.

11:34 Instead, you have to perform something

11:37 called a Discreet Fourier Transform.

11:40 And one of the distinguishing features

11:42 of a Discreet Fourier Transform

11:43 is that the frequency spectrum is also discreet and finite.

11:48 You can think of the frequencies

11:49 as falling into a finite number of bins.

11:53 And what determines the number and size of these bins

11:56 is the number of samples in the signal

11:58 and how closely spaced they are.

12:00 For example, the more spaced out the samples are,

12:03 the lower the maximum frequency you can measure.

12:06 Because the samples aren't close enough together

12:08 to capture high frequency oscillations,

12:12 the shorter the duration of the signal,

12:14 the harder it is to tell similar frequencies apart.

12:17 So this lowers the frequency resolution.

12:20 The shorter the signal, the wider each frequency bin is.

12:25 The lowest non-zero frequency you can effectively measure

12:28 is one whose period is equal to the duration of the signal.

12:32 And the higher frequency bins are just integer multiples

12:35 of this frequency.

12:36 So they fit two, three, four, and so on periods

12:40 in the duration of the signal.

12:42 The total number of frequency bins is equal

12:46 to the number of samples in the signal.

12:48 So if the signal is made up of eight samples,

12:51 then the transform has eight frequency bins

12:53 going from zero up to seven times the fundamental frequency.

12:58 So let's do an example.

13:00 Say we have a signal made up of eight samples.

13:03 Well, then the discrete Fourier transform

13:05 will have eight frequency bins.

13:08 The first bin corresponds to a frequency of zero.

13:11 Essentially this measures if the signal

13:13 is systematically shifted off the x-axis.

13:17 You can think of it as measuring the DC offset.

13:20 You multiply each data point by one

13:23 and add them all together, in this case, they add to zero.

13:28 The second frequency bin corresponds to the frequency

13:31 that fits one period in the duration of the signal.

13:34 So in this case that corresponds to one hertz.

13:37 You multiply each point by a sine wave of this frequency

13:41 and a cosine wave of this frequency

13:44 and separately add them up.

13:46 For sine, they add to zero.

13:48 For cosine, they add to four

13:51 and then repeat the process for two hertz, three hertz,

13:54 and so on, up to seven hertz.

13:57 And you have the discreet Fourier transform

14:00 of this really simple signal.

14:02 Now this process works fine in principle

14:05 and you could use it to calculate

14:07 all discrete Fourier transforms.

14:09 But the problem is it requires way too many calculations.

14:14 To complete one discrete Fourier transform

14:16 requires multiplying N data points

14:18 by N different frequency waves.

14:21 So N squared complex multiplications.

14:24 Now this is doable for eight samples

14:27 but if you had say a million samples,

14:30 that would require a million squared

14:32 or one trillion calculations.

14:37 At the speed of 1960s computers,

14:39 that would take over three years to complete,

14:42 all for a single transform.

14:44 Now a million samples is admittedly more than you would need

14:47 for a single seismic event but to analyze tens of events

14:50 per day from hundreds of seismometers,

14:53 it would just be far too time consuming

14:55 and that's what gave scientists the impetus

14:57 to look for a better way.

14:59 And the breakthrough came in 1963 at a meeting

15:02 of the President's Science Advisory Committee.

15:04 President John F. Kennedy was there,

15:06 as were Garwin and Tukey,

15:08 the physicist and mathematician from the Geneva meeting.

15:11 Although they were discussing issues of national importance

15:14 like the Apollo program and nuclear fallout shelters,

15:17 the meeting was apparently pretty boring.

15:19 Garwin observed Tukey doodling throughout

15:23 but what he was actually doing

15:25 was working on discreet Fourier transforms.

15:28 At the end of the meeting, Garwin asked Tukey

15:30 what he had worked out and he was shocked to learn

15:33 that Tukey knew a way to compute discreet Fourier transforms

15:36 with many fewer computations.

15:39 It would mean that the calculation that would've taken

15:40 over three years could be done in just 35 minutes.

15:45 This has aptly become known as the Fast Fourier Transform.

15:49 So here is how it works.

15:53 Consider the example from before with eight samples.

15:56 Each of those data points must be multiplied

15:58 by the eight different frequency waves.

16:00 Here I'm only showing cosines for simplicity.

16:04 So you would expect this to require eight times eight

16:06 or 64 complex multiplication.

16:10 But due to the periodic nature of sinusoids,

16:13 these waves of different frequencies

16:15 overlap in a predictable way.

16:17 For example, at the middle data point,

16:20 all of the four odd frequencies have the same value

16:23 and all of the four even frequencies

16:25 have the same value as well.

16:27 So instead of doing eight multiplication,

16:29 you only need to do two.

16:32 And this sort of duplication occurs

16:33 at the other data points as well.

16:35 So instead of performing 64 calculations, you need only 24.

16:41 Now that might seem like a small improvement

16:44 but it's the difference between a calculation

16:46 that scales as N, the number of samples squared

16:49 versus one that scales as Nlog base two of N

16:52 which means the bigger the data set,

16:54 the greater the savings.

16:56 A signal with a thousand samples would require

16:59 100 times fewer calculations and a million samples

17:03 would require 50,000 times fewer calculations.

17:08 But how do you know which calculations are redundant?

17:12 Well, take your samples and split them

17:15 into even and odd index points.

17:18 You still need to multiply

17:20 each of these by the eight different frequency waves.

17:23 But now let's look only at the even points and compare

17:26 the first four frequencies to the second four frequencies.

17:31 And what you find is that in each case

17:33 at the location of the samples,

17:35 the values of the two sine waves are the same.

17:39 A similar pattern can be observed for the odd index points

17:43 except the values of one sine wave are the negative

17:46 of the other.

17:47 More generally, they're related by a complex number.

17:51 But what this means is that you don't have to do

17:54 all the multiplication for the second half

17:57 of the frequencies.

17:58 Once you've calculated the odd and even sums

18:01 for the lower half the frequencies,

18:03 you can reuse these values to find the upper half.

18:08 So you've effectively cut the number of calculations

18:10 required in half but that's only a factor of two,

18:15 how do you get down to Nlog base two of N?

18:18 Well, you repeat the same trick,

18:20 split the samples again into even an odd points

18:24 and then again repeatedly

18:26 until you're down to single data points.

18:30 At each split, you can exploit the symmetries

18:32 of sinusoidal functions to cut the number of calculations

18:35 in half.

18:37 And that is how the Fast Fourier Transform reduces

18:40 N squared calculations down to NlogN.

18:44 And it's why today whenever anyone takes

18:45 a Fourier transform, it's almost always done

18:48 as a Fast Fourier Transform.

18:52 Garwin approached an IBM researcher, James Cooley

18:54 to program a computer to run the FFT algorithm

18:58 but he didn't tell him the reason was to detect

19:00 underground Soviet nuclear tests.

19:02 He said it was to work out the spins

19:04 in a crystal of helium-3.

19:06 Cooley and Tukey published the algorithm

19:08 in a seminal 1965 paper and its use immediately took off

19:13 but it was too late to secure

19:16 a comprehensive nuclear test ban.

19:19 By that time, the U.K., France and China

19:21 had joined the Soviet Union and the U.S. as nuclear powers.

19:27 And the partial test ban treaty,

19:28 far from deescalating the nuclear arms race

19:31 just sent it underground.

19:33 The thinking was if you were only allowed

19:35 to test underground, then you better be testing extensively

19:39 so as not to fall behind all the other nuclear states.

19:42 So from 1963, 1,500 nuclear weapons were detonated.

19:47 That's roughly one a week for 30 years.

19:50 This testing facilitated the construction

19:52 of an absurd number of nukes.

19:55 At the peak in the mid 1980s,

19:57 70,000 nuclear warheads were in existence.

20:01 Total expenditure on nukes in the 20th century

20:03 is estimated at around $10 trillion each for the U.S.

20:08 and the Soviet Union adjusting for inflation.

20:11 If only scientists had been confident in their ability

20:14 to remotely detect underground tests in the early 1960s,

20:17 then a comprehensive test ban could have been reached,

20:20 stopping the nuclear arms race before it really got going.

20:24 To check how realistic this is,

20:26 I asked Richard Garwin himself.

20:29 - Well, it's a good story.

20:32 - It is a good story.

20:33 - It would've helped and it might have turned the tide.

20:37 - But that would've required an earlier discovery

20:40 of the Fast Fourier Transform and as luck would have it,

20:43 it was discovered earlier but then forgotten.

20:48 All the way back in 1805, Mathematician Carl Friedrich Gauss

20:51 was studying the newly discovered asteroids

20:53 of Pallas, Ceres and Juno.

20:56 To determine the orbit of Juno,

20:57 Gauss devised a novel approach to harmonic analysis

21:00 and he jotted it down in his notes

21:02 but later used a different method

21:04 and he never thought to publish that first insight.

21:07 Today we can see that Gauss had figured out

21:10 the discreet Fourier Transform before Joseph Fourier himself

21:13 published it in 1807.

21:15 And he had developed the same Fast Fourier Transform

21:18 algorithm as Cooley and Tukey a century and a half earlier.

21:23 The reason his breakthrough was not widely adopted

21:25 was because it only appeared after his death in volume three

21:29 of his collected works and it was written with non-standard

21:32 notation in a 19th century version of Latin.

21:36 What do you think would've happened if Gauss had realized

21:39 the significance of his discovery and had published it

21:41 in a way that others could understand?

21:44 With our modern network of seismometers

21:46 and computing and the Fast Fourier Transform,

21:48 today, we have the ability to detect magnitude three events

21:51 which correspond to a one kilo ton or so explosion,

21:55 basically anywhere on earth.

21:58 Following Cooley and Tukey's paper, the use of FFTs exploded

22:02 and they are the basis for most compression algorithms

22:05 like the ones that allow you to watch

22:06 and listen to this video.

22:09 Here's how the Fast Fourier Transform

22:10 allows you to compress an image.

22:13 You take the pixel brightness values for each row

22:16 of an image and perform a Fast Fourier transform.

22:20 So essentially, you're figuring out what frequencies

22:23 are present in the brightness values

22:26 of the rows of an image.

22:27 Here, brightness represents the magnitude

22:30 of each frequency component and the color

22:32 represents the phase, how shifted that frequency is

22:35 to the left or the right.

22:37 And then you perform another FFT for the columns of pixels.

22:42 It doesn't matter if you do the rows or columns first,

22:45 which you need is a two dimensional FFT

22:48 of the original image.

22:50 For almost all real world images,

22:53 you find that a lot of the values in the transform

22:56 are close to zero.

22:58 I've taken the log of the transform values

23:00 so you can see them but if I don't, then it's clear

23:03 most of the values, especially toward the edges

23:05 are very small and these correspond to high frequencies.

23:10 And what this means is that you can throw out

23:12 a lot of the information in the transformed image

23:15 say 99% of it.

23:17 But when you invert that result, you still get a fairly good

23:21 representation of the original image.

23:24 So on your computer, most of the images will be saved

23:27 in this form as a two dimensional Fast Fourier Transform

23:30 and then when you wanna look at the picture again,

23:32 the computer simply inverts the transform.

23:36 There are so many applications for FFTs

23:38 from solving differential equations to radar and sonar,

23:42 studying crystal structures, WiFi and 5G.

23:45 Basically all kinds of signal processing use FFTs

23:49 and that's why mathematician Gilbert Strang called the FFT

23:52 the most important numerical algorithm of our lifetime.

23:56 If only it had become more widely adopted

23:59 after Gauss discovered it,

24:00 the FFT may have even more dramatically

24:03 transformed our world.

24:11 Now I don't think Gauss could ever have imagined

24:13 how important the FFT would be,

24:15 just as most people don't think about the cumulative impact

24:18 of their life's work.

24:19 You know in an average career, you work 40 hours a week,

24:23 50 weeks a year for 40 years

24:25 and that works out to 80,000 hours.

24:28 It means that your career might be your biggest opportunity

24:32 to make a difference in the world.

24:33 So what do you wanna do with all that time?

24:36 Now the name of this video sponsor is 80,000 Hours

24:40 referencing the amount of impact you can have,

24:42 the amount of hours you spend at work,

24:44 and they are not selling anything.

24:46 80,000 Hours is a nonprofit that helps people

24:48 find fulfilling careers that make a positive impact.

24:52 The typical advice from career centers or aptitude tests

24:55 really just focuses on finding a job

24:56 that fits your personal preferences.

24:58 But what if you care more about doing good?

25:01 Well, they won't really know what to tell you

25:03 besides a few well known professions

25:04 like being a doctor or a teacher.

25:06 When I finished college, I knew I liked filmmaking, teaching

25:10 and science and that I wanted to have a big positive impact

25:13 but YouTube didn't exist yet and so I honestly had no idea

25:17 what I was gonna do.

25:18 Now I feel really fortunate to be able to do something

25:21 every day that I both enjoy

25:23 and which makes a positive impact on the world.

25:25 So believe me, there are a lot of things out there

25:28 that you can do and 80,000 Hours offers tons of resources

25:31 to help you find those things.

25:33 From research backed guides on how to pick a career

25:35 that tackles pressing issues

25:37 to a regular newsletter and podcast.

25:39 They even have a curated job board that's kept up to date

25:42 with hundreds of jobs they think will make an impact.

25:45 They have done over 10 years of research alongside academics

25:48 at Oxford University on how to find a career that is both

25:51 fulfilling and which makes a positive difference.

25:54 So their recommendations are accurate, specific,

25:56 and actionable.

25:57 If you care about what the evidence says

25:59 about having an impactful career and you want real advice

26:02 that goes beyond empty cliches like follow your passion,

26:05 then check out 80,000 Hours.

26:07 Everything they provide from their podcast

26:09 to their job board is free forever.

26:12 If you join the newsletter right now,

26:13 you'll also get a free copy of their in-depth career guide

26:16 sent right to your inbox.

26:17 So to get started on a career that tackles

26:19 the world's most pressing problems,

26:21 sign up now at 80000hours.org/veritasium.

26:25 I will put that link down in the description.

26:27 So I wanna thank 80,000 Hours

26:29 for sponsoring this part of the video

26:30 and I wanna thank you for watching.

0:00 Đây là video về một thuật toán quan trọng nhất từ trước đến nay: Biến đổi Fourier Nhanh, hay còn gọi là FFT.

0:07 Ý tôi là, bạn dùng nó thường xuyên lắm, ngay cả bây giờ khi đang xem video này. Nó còn được dùng trong radar, sonar, 5G và WiFi nữa.

0:15 Về cơ bản, cứ khi nào có xử lý tín hiệu thì rất có thể là có sự tham gia của Biến đổi Fourier Nhanh.

0:21 Nhưng thú vị nhất là FFT được các nhà khoa học phát hiện ra khi họ cố gắng tìm cách phát hiện các vụ thử vũ khí hạt nhân bí mật.

0:28 Và nếu họ tìm ra nó sớm hơn, có lẽ nó đã có thể ngăn chặn được cuộc chạy đua vũ trang hạt nhân rồi.

0:36 Bạn biết đấy, tôi luôn nghĩ rằng cuộc chạy đua vũ trang hạt nhân là điều không thể tránh khỏi. Rằng một khi Mỹ ném bom nguyên tử xuống Hiroshima và Nagasaki, thì việc tất cả các cường quốc lớn khác phát triển vũ khí hạt nhân chỉ là vấn đề thời gian.

0:47 Nhưng có lẽ không phải vậy, vì ai cũng thấy rõ vũ khí hạt nhân đã thay đổi cuộc chơi.

0:54 Quả bom thả xuống Hiroshima giải phóng năng lượng gấp hàng nghìn lần so với chất nổ thông thường mạnh nhất, nên các nước khác lo ngại cũng là điều dễ hiểu.

1:03 Vào cuối chiến tranh, Canada và Anh đã yêu cầu một cuộc họp để thảo luận về việc phải làm gì với vũ khí hạt nhân.

1:09 Và trái với những gì tôi nghĩ, Mỹ thực sự cởi mở với những cuộc thảo luận này.

1:15 Họ nhận ra rằng họ sẽ không phải là quốc gia duy nhất sở hữu vũ khí hạt nhân lâu dài.

1:19 Vì vậy, họ đề nghị ngừng hoạt động tất cả vũ khí hạt nhân của mình nếu các quốc gia khác cam kết không bao giờ chế tạo chúng.

1:28 Đề xuất này được gọi là kế hoạch Baruch, trong đó đề xuất một cơ quan quốc tế sẽ kiểm soát tất cả các vật liệu phóng xạ trên trái đất, từ khâu khai thác, tinh chế cho đến sử dụng chúng cho các mục đích hòa bình như sản xuất điện hạt nhân.

1:43 Nhưng Liên Xô đã bác bỏ đề xuất này.

1:45 Họ coi đó chỉ là một chiêu trò khác để Mỹ duy trì vị thế thống trị hạt nhân của mình, và thế là cuộc chạy đua vũ trang hạt nhân toàn cầu bắt đầu.

1:55 Để phát triển vũ khí hạt nhân mới, cần phải thử nghiệm rộng rãi, và hầu hết các vụ thử đều được thực hiện ở những nơi xa xôi như Bắc Cực hoặc các đảo ở Nam Thái Bình Dương.

2:04 Mỹ cũng tạo ra một địa điểm thử nghiệm hạt nhân ở Nevada, và các sản phẩm phóng xạ từ đó đã lan rộng khắp đất nước. Vì vậy, ngoài Nhật Bản, những người bị ảnh hưởng nặng nề nhất bởi vũ khí hạt nhân của Mỹ lại chính là người Mỹ.

2:18 Sau đó, Mỹ nhanh chóng chuyển từ vũ khí phân hạch sang bom nhiệt hạch, kết hợp cả phân hạch và hợp hạch để giải phóng nhiều năng lượng hơn.

2:28 Chúng là một bước tiến lớn so với những quả bom nguyên tử đầu tiên, mạnh hơn gấp nghìn lần so với chất nổ thông thường.

2:37 - Khả năng hủy diệt mọi sự sống trên trái đất đã trở thành một khả năng kỹ thuật.

2:48 - Năm 1954, tại đảo san hô Bikini ở Nam Thái Bình Dương, Mỹ đã thử nghiệm một thiết kế nhiệt hạch mới sử dụng lithium deuteride làm nhiên liệu. Họ dự kiến thiết bị có mật danh "Tôm" sẽ giải phóng năng lượng tương đương sáu triệu tấn TNT, nhưng họ đã tính sai.

3:04 (tiếng bom nổ)

3:09 Nó đã giải phóng năng lượng gấp hai lần rưỡi so với dự kiến do các phản ứng không lường trước được với lithium-7.

3:15 Và kết quả là, một lượng lớn vật liệu phóng xạ đã được tạo ra và lan rộng ra một khu vực rộng lớn hơn nhiều so với dự kiến.

3:22 Cư dân của các đảo san hô lân cận chỉ được sơ tán ba ngày sau đó và bị nhiễm phóng xạ.

3:28 Xa hơn về phía đông, 23 thủy thủ trên một tàu đánh cá Nhật Bản đã bị dính phải một trận mưa tro trắng phóng xạ.

3:34 Đến tối hôm đó, họ đã bị hội chứng nhiễm xạ cấp tính.

3:39 Một trong những thủy thủ đã chết vì các biến chứng sau đó sáu tháng.

3:42 - Do bệnh kéo dài vì tiếp xúc với bụi phóng xạ.

3:48 - Những sự kiện này đã gây ra sự phẫn nộ trong dư luận về các cuộc thử nghiệm hạt nhân.

3:52 Biểu tượng hòa bình hiện đại được thiết kế vào những năm 1950 bằng cách kết hợp các chữ cái semaphore cho N và D, viết tắt của "giải trừ hạt nhân".

4:01 Một số nhà lãnh đạo thế giới đã kêu gọi một lệnh cấm thử nghiệm toàn diện, không còn quốc gia nào được thử nghiệm vũ khí hạt nhân nữa. Lời kêu gọi này đã được các cường quốc hạt nhân trên thế giới xem xét rất nghiêm túc.

4:13 Họ đã tham gia vào các cuộc đàm phán tại các cuộc họp với những cái tên rất sát nghĩa như "Hội nghị về việc ngừng thử nghiệm vũ khí hạt nhân" được tổ chức tại Geneva năm 1958.

4:24 Và để chứng minh sự nghiêm túc của mình, họ thậm chí đã ngừng tất cả các cuộc thử nghiệm trong thời gian đàm phán. Đó là lý do tại sao năm 1959 là năm duy nhất trong một thời gian dài không có vũ khí hạt nhân nào bị kích nổ.

4:36 Nhưng có một vấn đề lớn với việc đàm phán một lệnh cấm thử nghiệm toàn diện: làm sao bạn biết rằng bên kia sẽ giữ lời hứa?

4:46 Mỹ lo ngại rằng Liên Xô sẽ tiếp tục

4:48 thử nghiệm bí mật và vượt mặt họ về mặt công nghệ, và Liên Xô cũng không tin tưởng Mỹ.

4:55 Vì vậy, để giải quyết những lo ngại này, họ đã triệu tập "Hội nghị các chuyên gia để nghiên cứu khả năng phát hiện các hành vi vi phạm một thỏa thuận có thể có về việc đình chỉ các cuộc thử nghiệm hạt nhân".

5:06 Thật đấy, đó là tên thật của nó, tôi không bịa đâu.

5:13 Việc phát hiện các thử nghiệm trong khí quyển khá đơn giản.

5:16 Các đồng vị phóng xạ mà chúng tạo ra sẽ phân tán trong khí quyển và có thể được phát hiện cách xa hàng nghìn km.

5:23 Các vụ thử dưới nước tạo ra những âm thanh đặc biệt lan truyền hiệu quả ở độ sâu khoảng một km dưới mặt nước, và chúng có thể được thu bằng hydrophone.

5:33 Nhưng các vụ thử dưới lòng đất khó phát hiện từ xa hơn nhiều vì bức xạ của chúng hầu như bị giữ lại. Hơn nữa, Liên Xô từ chối cho phép các chuyến thăm kiểm tra tại chỗ, vì họ coi đó là hoạt động gián điệp.

5:46 Và đó là lý do tại sao khi hiệp ước cấm thử nghiệm được ký kết vào năm 1963, nó chỉ là một lệnh cấm một phần.

5:53 Nó cấm thử nghiệm dưới nước, trong khí quyển và trong không gian, những nơi có thể xác minh được việc tuân thủ. Nhưng nó không cấm thử nghiệm dưới lòng đất vì đơn giản là gần như không thể xác minh.

6:06 Tuy nhiên, các nhà khoa học vẫn cố gắng tìm ra cách để phát hiện đáng tin cậy các vụ nổ dưới lòng đất.

6:11 Sau cuộc họp ở Geneva, các nhà khoa học Mỹ và Liên Xô đã thành lập một nhóm làm việc để thảo luận về vấn đề này. Ý tưởng của họ là sử dụng máy đo địa chấn đặt bên ngoài các quốc gia đang thử nghiệm vũ khí hạt nhân để phát hiện các rung động yếu do các vụ nổ gây ra.

6:27 Vấn đề là, làm sao để phân biệt một vụ thử hạt nhân với một trận động đất?

6:32 Mỗi ngày trên thế giới có gần 300 trận động đất có cường độ từ ba trở lên.

6:39 Ngoài ra, một phần mục đích của việc phát hiện các cuộc thử nghiệm của đối thủ là để theo dõi họ, để biết họ có thể tạo ra một vụ nổ lớn đến mức nào.

6:47 Nhưng tín hiệu máy đo địa chấn không chỉ phụ thuộc vào sức công phá của thiết bị mà còn phụ thuộc vào độ sâu mà nó được chôn.

6:54 Với cùng một sức công phá, các vụ nổ ở độ sâu lớn hơn có vẻ nhỏ hơn.

6:58 Vì vậy, các nhà khoa học muốn một phương pháp để xác định một cách đáng tin cậy xem một tín hiệu nhất định là bom hay động đất, và nếu là bom, thì nó lớn đến mức nào và được chôn sâu bao nhiêu.

7:09 Họ biết rằng tất cả thông tin này đều nằm trong tín hiệu máy đo địa chấn, nhưng không thể chỉ đọc được bằng cách nhìn vào các đường ngoằn ngoèo.

7:16 Họ cần biết có bao nhiêu tần số khác nhau, và điều đó có nghĩa là họ cần thực hiện biến đổi Fourier.

7:25 Biến đổi Fourier là một cách phân tích một tín hiệu thành các sóng sin thuần túy, mỗi sóng có biên độ và tần số riêng, cộng lại để tạo thành tín hiệu đó.

7:35 Điều này có vẻ hơi kỳ diệu vì tổng của một tập hợp các sóng sin có thể trông phức tạp tùy ý và không giống bất kỳ bộ phận cấu thành nào của nó.

7:44 Có một số cách hay để hiểu cách biến đổi Fourier hoạt động, và tôi xin giới thiệu video tuyệt vời của 3Blue1Brown.

7:50 Nhưng tôi muốn tiếp cận theo kiểu "ăn xổi" hơn.

7:53 Nếu bạn muốn biết có bao nhiêu sóng sin cụ thể trong một tín hiệu, chỉ cần nhân tín hiệu đó với sóng sin tại mỗi điểm, sau đó cộng diện tích dưới đường cong.

8:05 Ví dụ đơn giản, giả sử tín hiệu của chúng ta chỉ là một sóng sin với một tần số nhất định, nhưng cứ cho là chúng ta không biết điều đó và đang cố gắng tìm ra những sóng sin nào cộng lại để tạo thành nó.

8:15 Nếu bạn nhân tín hiệu này với một sóng sin có tần số tùy ý, thì hai sóng này không tương quan.

8:22 Bạn có thể tìm thấy những chỗ chúng có cùng dấu, cả dương hoặc cả âm, cũng như những chỗ chúng có dấu trái ngược nhau. Do đó, khi bạn nhân chúng lại với nhau, diện tích phía trên trục x bằng diện tích phía dưới trục x.

8:35 Vì vậy, các diện tích này cộng lại bằng không, có nghĩa là sóng sin tần số đó không phải là một phần của tín hiệu của bạn. Điều này sẽ đúng với hầu hết tất cả các tần số bạn có thể thử, miễn là bạn đang xem xét trong một khung thời gian đủ dài.

8:48 Ngoại lệ duy nhất là nếu tần số của sóng sin khớp chính xác với tần số của tín hiệu. Lúc này, các sóng này tương quan, vì vậy tích của chúng luôn dương và diện tích dưới đường cong cũng vậy, cho thấy sóng sin này là một phần của tín hiệu của chúng ta.

9:06 Và thủ thuật này hoạt động ngay cả khi tín hiệu bao gồm một loạt các tần số khác nhau.

9:10 Nếu tần số sóng sin là một trong các thành phần của tín hiệu, nó sẽ tương quan với tín hiệu, tạo ra một diện tích khác không.

9:17 Và kích thước của diện tích này cho bạn biết biên độ tương đối

9:20 của sóng sin tần số đó trong tín hiệu.

9:24 Lặp lại quá trình này cho tất cả các tần số của sóng sin và bạn sẽ nhận được phổ tần số, về cơ bản là tần số nào có mặt và theo tỷ lệ nào.

9:35 Đến giờ tôi chỉ nói về sóng sin, nhưng nếu tín hiệu là sóng cosin, thì ngay cả khi bạn nhân nó với một sóng sin có cùng tần số chính xác, diện tích dưới đường cong sẽ bằng không.

9:47 Vì vậy, đối với mỗi tần số, chúng ta thực sự cần nhân với cả sóng sin và sóng cosin, rồi tìm biên độ cho mỗi sóng.

9:55 Tỷ lệ của các biên độ này cho biết pha của tín hiệu, tức là nó đã bị dịch chuyển sang trái hoặc sang phải bao nhiêu.

10:03 Bạn có thể tính toán các biên độ sin và cosin này riêng biệt, hoặc bạn có thể sử dụng công thức Euler, để chỉ cần nhân tín hiệu của mình với một số mũ.

10:13 Sau đó, phần thực của tổng là biên độ cosin và phần ảo là biên độ sin.

10:20 Trong phái đoàn Mỹ tại cuộc họp ở Geneva có một nhà vật lý, Richard Garwin, và một nhà toán học, John Tukey.

10:27 Họ đã tranh luận với phái đoàn Liên Xô về việc máy đo địa chấn của quốc gia nào tốt hơn.

10:32 Vì vậy, Garwin đã mô phỏng các phản ứng của các thiết bị của cả hai quốc gia trên máy tính tại CERN.

10:39 Ngày hôm sau, mọi người đều đồng ý rằng không có nhiều khác biệt giữa các thiết bị.

10:43 Trở ngại thực sự để phát hiện các vụ nổ dưới lòng đất không phải là độ chính xác của máy đo địa chấn, mà là lượng tính toán khổng lồ cần thiết để biến đổi Fourier các tín hiệu máy đo địa chấn.

10:56 Đây là một ví dụ về tín hiệu máy đo địa chấn và biến đổi Fourier của nó.

11:00 Đến giờ, tôi vẫn đang nói về các tín hiệu như những sóng liên tục vô tận. Và khi bạn thực hiện biến đổi Fourier của chúng, bạn sẽ nhận được một phổ tần số liên tục vô tận.

11:09 Nhưng các tín hiệu trong thế giới thực không phải như vậy.

11:12 Chúng là hữu hạn và được tạo thành từ các mẫu hoặc điểm dữ liệu riêng lẻ.

11:16 Mặc dù tín hiệu máy đo địa chấn trông mượt mà và liên tục, nhưng nó không ghi lại chuyển động của mặt đất với độ chính xác tuyệt đối.

11:24 Có một giới hạn nhất định đối với độ chi tiết của dữ liệu. Vì vậy, những gì bạn có là dữ liệu hữu hạn rời rạc.

11:30 Do đó, bạn không thể sử dụng biến đổi Fourier lý tưởng.

11:34 Thay vào đó, bạn phải thực hiện một thứ gọi là Biến đổi Fourier Rời rạc.

11:40 Và một trong những đặc điểm của Biến đổi Fourier Rời rạc là phổ tần số cũng rời rạc và hữu hạn.

11:48 Bạn có thể coi các tần số như rơi vào một số lượng hữu hạn các "bin" (khoảng).

11:53 Và điều xác định số lượng và kích thước của các bin này là số lượng mẫu trong tín hiệu và khoảng cách giữa chúng.

12:00 Ví dụ, các mẫu càng cách xa nhau, tần số tối đa bạn có thể đo càng thấp, vì các mẫu không đủ gần nhau để ghi lại các dao động tần số cao.

12:12 Thời gian của tín hiệu càng ngắn, càng khó phân biệt các tần số tương tự.

12:17 Vì vậy, điều này làm giảm độ phân giải tần số.

12:20 Tín hiệu càng ngắn, mỗi bin tần số càng rộng.

12:25 Tần số khác không thấp nhất mà bạn có thể đo hiệu quả là tần số có chu kỳ bằng thời gian của tín hiệu.

12:32 Và các bin tần số cao hơn chỉ là bội số nguyên của tần số này.

12:36 Vì vậy, chúng tương ứng với hai, ba, bốn, v.v. chu kỳ trong thời gian của tín hiệu.

12:42 Tổng số bin tần số bằng số lượng mẫu trong tín hiệu.

12:48 Vì vậy, nếu tín hiệu được tạo thành từ tám mẫu, thì phép biến đổi sẽ có tám bin tần số, đi từ không lên đến bảy lần tần số cơ bản.

12:58 Chúng ta hãy làm một ví dụ.

13:00 Giả sử chúng ta có một tín hiệu được tạo thành từ tám mẫu.

13:03 Thì biến đổi Fourier rời rạc sẽ có tám bin tần số.

13:08 Bin đầu tiên tương ứng với tần số bằng không.

13:11 Về cơ bản, nó đo xem tín hiệu có bị dịch chuyển một cách có hệ thống khỏi trục x hay không.

13:17 Bạn có thể coi nó như đo độ lệch DC.

13:20 Bạn nhân mỗi điểm dữ liệu với một và cộng tất cả chúng lại với nhau; trong trường hợp này, chúng cộng lại bằng không.

13:28 Bin tần số thứ hai tương ứng với tần số phù hợp với một chu kỳ trong thời gian của tín hiệu.

13:34 Trong trường hợp này, nó tương ứng với một hertz.

13:37 Bạn nhân mỗi điểm với một sóng sin có tần số này và một sóng cosin có tần số này, rồi cộng chúng lại riêng biệt.

13:46 Đối với sin, chúng cộng lại bằng không.

13:48 Đối với cosin, chúng cộng lại bằng bốn. Sau đó, lặp lại quá trình cho hai hertz, ba hertz, v.v., lên đến bảy hertz.

13:57 Và bạn có biến đổi Fourier rời rạc của tín hiệu thực sự đơn giản này.

14:02 Về nguyên tắc, quá trình này hoạt động tốt và bạn có thể sử dụng nó để tính toán tất cả các biến đổi Fourier rời rạc.

14:09 Nhưng vấn đề là nó đòi hỏi quá nhiều tính toán.

14:14 Để hoàn thành một biến đổi Fourier rời rạc, bạn cần nhân N điểm dữ liệu với N sóng tần số khác nhau, tức là cần N bình phương phép nhân phức.

14:24 Điều này có thể thực hiện được đối với tám mẫu, nhưng nếu bạn có một triệu mẫu, thì sẽ cần một triệu bình phương, hay một nghìn tỷ phép tính.

14:37 Với tốc độ của máy tính những năm 1960, sẽ mất hơn ba năm để hoàn thành, chỉ cho một phép biến đổi duy nhất.

14:44 Một triệu mẫu rõ ràng là nhiều hơn mức bạn cần cho một sự kiện địa chấn duy nhất. Nhưng để phân tích hàng chục sự kiện mỗi ngày từ hàng trăm máy đo địa chấn, nó sẽ tốn quá nhiều thời gian. Đó là điều đã thúc đẩy các nhà khoa học tìm kiếm một cách tốt hơn.

14:59 Và bước đột phá đến vào năm 1963 tại một cuộc họp của Ủy ban Cố vấn Khoa học của Tổng thống.

15:04 Tổng thống John F. Kennedy đã ở đó, cũng như Garwin và Tukey, nhà vật lý và nhà toán học từ cuộc họp ở Geneva.

15:11 Mặc dù họ đang thảo luận về các vấn đề quan trọng quốc gia như chương trình Apollo và hầm trú ẩn hạt nhân, nhưng cuộc họp dường như khá nhàm chán.

15:19 Garwin quan sát thấy Tukey đang vẽ nguệch ngoạc trong suốt buổi họp. Nhưng thực ra, ông ấy đang nghiên cứu các biến đổi Fourier rời rạc.

15:28 Vào cuối cuộc họp, Garwin hỏi Tukey về những gì ông ấy đã làm. Ông ấy đã rất sốc khi biết rằng Tukey biết một cách để tính toán các biến đổi Fourier rời rạc với ít phép tính hơn nhiều.

15:39 Điều đó có nghĩa là phép tính lẽ ra phải mất hơn ba năm có thể được thực hiện chỉ trong 35 phút.

15:45 Phát minh này đã được đặt tên một cách thích hợp là Biến đổi Fourier Nhanh.

15:49 Vậy, nó hoạt động như thế nào?

15:53 Hãy xem lại ví dụ trước với tám mẫu.

15:56 Mỗi điểm dữ liệu đó phải được nhân với tám sóng tần số khác nhau.

16:00 Ở đây tôi chỉ hiển thị cosin cho đơn giản.

16:04 Vì vậy, bạn có thể nghĩ rằng điều này sẽ yêu cầu tám lần tám, hay 64 phép nhân phức.

16:10 Nhưng do bản chất tuần hoàn của các sóng sin, các sóng có tần số khác nhau này chồng lên nhau theo một cách có thể dự đoán được.

16:17 Ví dụ, tại điểm dữ liệu giữa, tất cả bốn tần số lẻ đều có cùng giá trị, và tất cả bốn tần số chẵn cũng có cùng giá trị.

16:27 Vì vậy, thay vì thực hiện tám phép nhân, bạn chỉ cần thực hiện hai phép nhân.

16:32 Và sự trùng lặp này cũng xảy ra ở các điểm dữ liệu khác.

16:35 Vì vậy, thay vì thực hiện 64 phép tính, bạn chỉ cần 24 phép tính.

16:41 Nghe có vẻ như một cải tiến nhỏ, nhưng đó là sự khác biệt giữa một phép tính tỷ lệ theo N bình phương (N là số lượng mẫu), so với một phép tính tỷ lệ theo Nlog cơ số hai của N. Điều đó có nghĩa là tập dữ liệu càng lớn, bạn càng tiết kiệm được nhiều.

16:56 Một tín hiệu với một nghìn mẫu sẽ yêu cầu ít hơn 100 lần tính toán, và một triệu mẫu sẽ yêu cầu ít hơn 50.000 lần tính toán.

17:08 Nhưng làm sao bạn biết những phép tính nào là dư thừa?

17:12 Hãy lấy các mẫu của bạn và chia chúng thành các điểm có chỉ số chẵn và lẻ.

17:18 Bạn vẫn cần nhân mỗi điểm này với tám sóng tần số khác nhau.

17:23 Nhưng bây giờ chúng ta hãy chỉ nhìn vào các điểm chẵn và so sánh bốn tần số đầu tiên với bốn tần số thứ hai.

17:31 Trong mỗi trường hợp, tại vị trí của các mẫu, các giá trị của hai sóng sin là như nhau.

17:39 Một mô hình tương tự có thể được quan sát thấy đối với các điểm có chỉ số lẻ, ngoại trừ các giá trị của một sóng sin là âm của sóng kia.

17:47 Nói chung hơn, chúng có liên quan với nhau bởi một số phức.

17:51 Điều này có nghĩa là bạn không phải thực hiện tất cả các phép nhân cho nửa sau của các tần số.

17:58 Khi bạn đã tính toán các tổng lẻ và chẵn cho nửa dưới của các tần số, bạn có thể sử dụng lại các giá trị này để tìm nửa trên.

18:08 Vì vậy, bạn đã giảm hiệu quả số lượng tính toán cần thiết xuống một nửa, nhưng đó chỉ là hệ số hai.

18:15 Làm thế nào để bạn giảm xuống Nlog cơ số hai của N?

18:18 Bạn lặp lại thủ thuật tương tự, chia các mẫu một lần nữa thành các điểm chẵn và lẻ, và sau đó lặp lại cho đến khi bạn chỉ còn lại các điểm dữ liệu đơn lẻ.

18:30 Tại mỗi lần chia, bạn có thể khai thác các đối xứng của các hàm sin để cắt giảm số lượng tính toán xuống một nửa.

18:37 Và đó là cách Biến đổi Fourier Nhanh giảm các phép tính từ N bình phương xuống NlogN.

18:44 Đó là lý do tại sao ngày nay, bất cứ khi nào ai đó thực hiện

18:45 một biến đổi Fourier, nó hầu như luôn được thực hiện dưới dạng Biến đổi Fourier Nhanh.

18:52 Garwin đã tiếp cận một nhà nghiên cứu của IBM, James Cooley, để lập trình một máy tính để chạy thuật toán FFT. Nhưng ông không nói với Cooley rằng mục đích là để phát hiện các vụ thử hạt nhân ngầm của Liên Xô.

19:02 Ông nói rằng đó là để tìm ra các vòng quay trong một tinh thể helium-3.

19:06 Cooley và Tukey đã công bố thuật toán này trong một bài báo mang tính bước ngoặt vào năm 1965, và nó đã được sử dụng rộng rãi ngay lập tức. Nhưng đã quá muộn để đảm bảo một lệnh cấm thử nghiệm hạt nhân toàn diện.

19:19 Vào thời điểm đó, Anh, Pháp và Trung Quốc đã gia nhập Liên Xô và Mỹ với tư cách là các cường quốc hạt nhân.

19:27 Hiệp ước cấm thử nghiệm một phần không những không làm giảm leo thang cuộc chạy đua vũ trang hạt nhân, mà còn đẩy nó xuống lòng đất.

19:33 Suy nghĩ là, nếu bạn chỉ được phép thử nghiệm dưới lòng đất, thì tốt hơn hết là bạn nên thử nghiệm rộng rãi để không bị tụt lại phía sau các quốc gia hạt nhân khác.

19:42 Vì vậy, từ năm 1963, 1.500 vũ khí hạt nhân đã bị kích nổ.

19:47 Đó là khoảng một vũ khí mỗi tuần trong 30 năm.

19:50 Thử nghiệm này đã tạo điều kiện cho việc xây dựng một số lượng vũ khí hạt nhân vô lý.

19:55 Vào thời kỳ đỉnh cao vào giữa những năm 1980, có tới 70.000 đầu đạn hạt nhân.

20:01 Tổng chi phí cho vũ khí hạt nhân trong thế kỷ 20 ước tính vào khoảng 10 nghìn tỷ đô la cho mỗi nước Mỹ và Liên Xô, sau khi đã điều chỉnh theo lạm phát.

20:11 Nếu các nhà khoa học tự tin vào khả năng phát hiện từ xa các cuộc thử nghiệm dưới lòng đất vào đầu những năm 1960, thì một lệnh cấm thử nghiệm toàn diện có lẽ đã đạt được, ngăn chặn cuộc chạy đua vũ trang hạt nhân trước khi nó thực sự bắt đầu.

20:24 Để kiểm tra xem điều này có thực tế hay không, tôi đã hỏi chính Richard Garwin.

20:29 Chà, đó là một câu chuyện hay.

20:32 Đó là một câu chuyện hay.

20:33 Nó sẽ giúp ích và có thể đã xoay chuyển tình thế.

20:37 Nhưng điều đó sẽ đòi hỏi một khám phá sớm hơn về Biến đổi Fourier Nhanh. Thật không may, nó đã được khám phá sớm hơn nhưng sau đó bị lãng quên.

20:48 Trở lại năm 1805, nhà toán học Carl Friedrich Gauss đang nghiên cứu các tiểu hành tinh mới được phát hiện Pallas, Ceres và Juno.

20:56 Để xác định quỹ đạo của Juno, Gauss đã nghĩ ra một phương pháp mới để phân tích hài hòa, và ông đã ghi lại nó trong các ghi chú của mình. Nhưng sau đó, ông đã sử dụng một phương pháp khác, và không bao giờ nghĩ đến việc công bố phát hiện ban đầu đó.

21:07 Ngày nay, chúng ta có thể thấy rằng Gauss đã tìm ra Biến đổi Fourier rời rạc trước khi chính Joseph Fourier công bố nó vào năm 1807.

21:15 Và ông đã phát triển cùng một thuật toán Biến đổi Fourier Nhanh như Cooley và Tukey một thế kỷ rưỡi trước đó.

21:23 Lý do bước đột phá của Gauss không được áp dụng rộng rãi là vì nó chỉ xuất hiện sau khi ông qua đời trong tập ba của các tác phẩm được thu thập của ông. Hơn nữa, nó được viết bằng ký hiệu không chuẩn trong một phiên bản tiếng Latinh thế kỷ 19.

21:36 Bạn nghĩ điều gì sẽ xảy ra nếu Gauss nhận ra tầm quan trọng của khám phá của mình và công bố nó theo cách mà người khác có thể hiểu được?

21:44 Với mạng lưới máy đo địa chấn và máy tính hiện đại của chúng ta, cùng với Biến đổi Fourier Nhanh, ngày nay chúng ta có khả năng phát hiện các sự kiện có cường độ ba (tương ứng với một vụ nổ khoảng một kiloton) ở hầu hết mọi nơi trên trái đất.

21:58 Sau bài báo của Cooley và Tukey, việc sử dụng FFT đã bùng nổ. Chúng là cơ sở cho hầu hết các thuật toán nén, ví dụ như những thuật toán cho phép bạn xem và nghe video này.

22:09 Đây là cách Biến đổi Fourier Nhanh cho phép bạn nén một hình ảnh.

22:13 Bạn lấy các giá trị độ sáng pixel cho mỗi hàng của hình ảnh và thực hiện Biến đổi Fourier Nhanh.

22:20 Về cơ bản, bạn đang tìm ra những tần số nào có trong các giá trị độ sáng của các hàng của hình ảnh.

22:27 Ở đây, độ sáng đại diện cho độ lớn của mỗi thành phần tần số, và màu sắc đại diện cho pha, tức là tần số đó được dịch chuyển sang trái hay sang phải bao nhiêu.

22:37 Sau đó, bạn thực hiện một FFT khác cho các cột pixel.

22:42 Không quan trọng bạn thực hiện các hàng hay cột trước. Điều quan trọng là bạn cần FFT hai chiều của hình ảnh gốc.

22:50 Đối với hầu hết các hình ảnh trong thế giới thực, bạn sẽ thấy rằng rất nhiều giá trị trong phép biến đổi gần bằng không.

22:58 Tôi đã lấy log của các giá trị biến đổi để bạn có thể nhìn thấy chúng. Nếu không, rõ ràng là hầu hết các giá trị, đặc biệt là ở phía các cạnh, là rất nhỏ và chúng tương ứng với các tần số cao.

23:10 Điều này có nghĩa là bạn có thể loại bỏ rất nhiều thông tin trong hình ảnh đã chuyển đổi, chẳng hạn như 99% thông tin đó.

23:17 Nhưng khi bạn đảo ngược kết quả đó, bạn vẫn nhận được một

23:21 hình ảnh khá giống với hình ảnh gốc.

23:24 Vì vậy, trên máy tính của bạn, hầu hết các hình ảnh sẽ được lưu ở dạng này dưới dạng Biến đổi Fourier Nhanh hai chiều. Sau đó, khi bạn muốn xem lại hình ảnh, máy tính chỉ cần đảo ngược phép biến đổi.

23:36 Có rất nhiều ứng dụng cho FFT, từ giải các phương trình vi phân đến radar và sonar, nghiên cứu cấu trúc tinh thể, WiFi và 5G.

23:45 Về cơ bản, tất cả các loại xử lý tín hiệu đều sử dụng FFT. Đó là lý do tại sao nhà toán học Gilbert Strang gọi FFT là thuật toán số quan trọng nhất trong cuộc đời chúng ta.

23:56 Nếu nó được áp dụng rộng rãi hơn sau khi Gauss phát hiện ra nó, thì FFT có lẽ đã thay đổi thế giới của chúng ta một cách ấn tượng hơn nữa.

24:11 Tôi không nghĩ rằng Gauss có thể tưởng tượng được FFT sẽ quan trọng đến mức nào. Cũng giống như hầu hết mọi người không nghĩ về tác động tích lũy của công việc cả đời của họ.

24:19 Trong một sự nghiệp trung bình, bạn làm việc 40 giờ một tuần, 50 tuần một năm trong 40 năm. Điều đó tương đương với 80.000 giờ.

24:28 Điều đó có nghĩa là sự nghiệp của bạn có thể là cơ hội lớn nhất để bạn tạo ra sự khác biệt trên thế giới.

24:33 Vậy bạn muốn làm gì với tất cả thời gian đó?

24:36 Tên của nhà tài trợ video này là 80.000 Giờ, đề cập đến lượng tác động bạn có thể tạo ra, số giờ bạn dành cho công việc. Và họ không bán bất cứ thứ gì.

24:46 80.000 Giờ là một tổ chức phi lợi nhuận giúp mọi người tìm thấy những sự nghiệp viên mãn, tạo ra tác động tích cực.

24:52 Lời khuyên điển hình từ các trung tâm nghề nghiệp hoặc các bài kiểm tra năng khiếu thường chỉ tập trung vào việc tìm một công việc phù hợp với sở thích cá nhân của bạn.

24:58 Nhưng nếu bạn quan tâm nhiều hơn đến việc làm điều tốt thì sao?

25:01 Họ sẽ không thực sự biết phải nói gì với bạn ngoài một vài nghề nghiệp phổ biến như bác sĩ hoặc giáo viên.

25:06 Khi tôi học xong đại học, tôi biết tôi thích làm phim, giảng dạy và khoa học, và tôi muốn tạo ra một tác động tích cực lớn. Nhưng YouTube vẫn chưa ra đời, vì vậy tôi thực sự không biết mình sẽ làm gì.

25:18 Bây giờ tôi cảm thấy thực sự may mắn khi có thể làm điều gì đó mỗi ngày mà tôi vừa thích vừa tạo ra tác động tích cực đến thế giới.

25:25 Hãy tin tôi, có rất nhiều điều bạn có thể làm. 80.000 Giờ cung cấp vô số tài nguyên để giúp bạn tìm thấy những điều đó.

25:33 Từ các hướng dẫn được nghiên cứu kỹ lưỡng về cách chọn một sự nghiệp giải quyết các vấn đề cấp bách đến một bản tin và podcast thường xuyên.

25:39 Họ thậm chí còn có một bảng việc làm được tuyển chọn, được cập nhật với hàng trăm công việc mà họ nghĩ sẽ tạo ra tác động.

25:45 Họ đã thực hiện hơn 10 năm nghiên cứu cùng với các học giả tại Đại học Oxford về cách tìm một sự nghiệp vừa viên mãn vừa tạo ra sự khác biệt tích cực.

25:54 Vì vậy, các khuyến nghị của họ là chính xác, cụ thể và có thể hành động.

25:57 Nếu bạn quan tâm đến những gì bằng chứng cho thấy về việc có một sự nghiệp có tác động, và bạn muốn lời khuyên thực tế vượt ra ngoài những câu sáo rỗng như "theo đuổi đam mê của bạn", thì hãy xem 80.000 Giờ.

26:07 Mọi thứ họ cung cấp, từ podcast đến bảng việc làm của họ, đều miễn phí mãi mãi.

26:12 Nếu bạn đăng ký bản tin ngay bây giờ, bạn cũng sẽ nhận được một bản sao miễn phí hướng dẫn nghề nghiệp chuyên sâu của họ, được gửi thẳng đến hộp thư đến của bạn.

26:17 Để bắt đầu một sự nghiệp giải quyết các vấn đề cấp bách nhất của thế giới, hãy đăng ký ngay bây giờ tại 80000hours(dot)org(slash)veritasium.

26:25 Tôi sẽ đặt liên kết đó ở phần mô tả bên dưới.

26:27 Cảm ơn 80.000 Giờ đã tài trợ cho video này, và cảm ơn các bạn đã theo dõi!