This article is the author’s study notes, please don’t comment if you don’t like them. This article contains a lot of content. If necessary, please click on the table of contents to skip some content. The flow chart in this article needs to be in a bright color style to see the arrows.
Prologue: Overall Concept
graph TD
A[调和分析:研究
“任何东西都能拆成波”
的学问] –> B[傅里叶级数
（周期信号）]
A –> C[傅里叶变换
（任意信号）]
A –> D[其他分解
（小波、拉普拉斯…）]
B –> E[离散傅里叶变换
DFT]
C –> E
E –> F[快速傅里叶变换
FFT]
One sentence summarizes the entire road: Harmonic analysis is the science of “splitting everything into waves”; Fourier transform is its most famous tool; DFT is the version for computers; FFT is the algorithm that makes DFT run fast.
1: What exactly is harmonic analysis?
1.1 Let’s look at a daily problem first
You hear a piece of music. What your ears hear is “the air vibrating.” But what you perceive in your mind is “piano, violin, drums, human voice.”
When the same piece of air vibrates, your ears automatically break it down into different “instruments” and “pitches”. Your ears are born to do harmonic analysis.
1.2 Where does the word “reconciling” come from?
“reconcile”(\(harmonic\)), the word first came from music.
When a string vibrates, it produces not just one note, but all at the same time:
- Fundamental note: The loudest note, which determines the pitch;
- Overtone: A sound that is an integral multiple of the fundamental tone, which determines the timbre.
基音： 频率 f ━━━━━━━━━━
第二泛音：频率 2f ━━━━━━━━━━━
第三泛音：频率 3f ━━━━━━━━━━━
第四泛音：频率 4f ━━━━━━━━━━━
...
These frequencies are sounds related to “integer multiples” and sound likeharmoniousso it’s called “reconciliation”.
Harmonic analysis is to study “whether a complex thing can be broken down into these harmonious waves.”
1.3 A more vivid term: prism
White light looks “white”, but when shined through a prism, it is actually red, orange, yellow, green, blue, indigo and violet mixed together.
graph TD
A[白光]–>B[三棱镜]
B–>C[红]
B–>D[橙]
B–>E[黄]
B–>F[绿]
B–>G[蓝]
B–>H[靛]
B–>I[紫]
Harmonic analysis ismathematical prism：
graph TD
A[复杂信号]–>B[调和分析]
B–>C[各种频率的波]
- White light = complex signal
- Prism = Fourier Transform
- Seven colors of light = frequency components
This is the core metaphor of the entire explanation, which will be used repeatedly later.
1.4 Three major issues in harmonic analysis
The core of the science of harmonious analysis is to answer three questions:
- Can it be dismantled? Can any signal be broken into waves?
- How to dismantle it? What is the method of disassembly?
- What’s the use of taking it apart? What can you do after taking it apart?
Fourier transform is the \(2\) The first and most famous answer to this question.
2: Fourier’s crazy idea
2.1 A young man who was laughed at
\(1807\) year, French mathematician Fourier submitted a paper with a startling assertion:
Any periodic signal, no matter how oddly shaped, can be broken down into a collection of sine and cosine waves.
Lagrange, the mathematical authority at the time, looked at it and said directly: “This is impossible. A square wave has edges and corners, and a sine wave is smooth. How can it be possible to spell it out?”
Twenty years later, people discovered that his method was not only correct, but also became the cornerstone of modern signal processing.
2.2 Why can square waves be spelled out?
Lagrange’s question is natural: a square wave is “straight up and down” and a sine wave is “bent”. How can they be the same?
The answer is:By superimposing many, many sine waves, the edges and corners will be “stacked” out.
Look at this process (no need to look at the formula!!!):
1 sine wave
\[S_1(x)=\frac{4}{\pi}\sin x
\]
3 sine waves superimposed
\[S_3(x)=\frac{4}{\pi}\left(\sin x+\frac{1}{3}\sin 3x+\frac{1}{5}\sin 5x\right)
\]
6 sine waves superimposed
\[S_6(x)=\frac{4}{\pi}\left(\sin x+\frac{1}{3}\sin 3x+\frac{1}{5}\sin 5x+\frac{1}{7}\sin 7x+\frac{1}{9}\sin 9x+\frac{1}{11}\sin 11x\right)
\]
Superposition of many sine waves
\[\cdot\cdot\cdot\cdot\cdot\space\cdot
\]
GIF
\[S_N(x)=\frac{4}{\pi}\sum_{m=0}^{N-1}\frac{\sin((2m+1)x)}{2m+1}
\]
It can be rigorously proven mathematically:When the number of sine waves approaches infinity, the superposition result is infinitely close to a square wave.
2.3 An important distinction: addition, not substitution
Note: Fourier saidOverlaynot “replace square wave with sine wave”.
\[方波 = 正弦1 + 正弦2 + 正弦3 + …
\]
Each sine wave is real, it’s just that they stack up and look like a square wave.
This is like:A symphony = violin sound + cello sound + flute sound + …
Each instrument is really playing, it’s just mixed together that what you hear is the “whole”.
3: Fourier series (FS)-decomposition method of periodic signals
3.1 First limit: only remove signals that “will repeat”
The Fourier series only deals with one type of signal:periodic signalthat is, a signal that will be repeated over and over again.
for example:
electrocardiogram
sine wave
square wave
These things will “come around again and again.”
3.2 What does the removed “signal” look like?
There are only two waveforms used in Fourier series:
- sine wave（\(sin\)）
- cosine wave（\(cos\)）
They are all waves that “smoothly move up and down.”
Moreover, the frequencies used are all “integer multiples”:
It’s like Lego bricks:Use building blocks of the same size to create various shapes.
3.3 How much information is required for each waveform?
A sine wave can be completely determined with only two pieces of information:
- How loud(Amplitude): How high the wave is;
- where to start(Phase): The wave is from \(0\) Start from the highest point.
Therefore, the result is a table:
| frequency | How loud | where to start |
|---|---|---|
| \(1f\) | \(2.0\) | \(0°\) |
| \(2f\) | \(0.5\) | \(90°\) |
| \(3f\) | \(0.3\) | \(180°\) |
| … | … | … |
This table isSpectrum。
3.4 Imagery: the choir
Think of the Fourier series as a choir:
- Each singer is responsible for one frequency;
- Each singer has his or her own volume (amplitude);
- Each singer has his own timing (phase) of singing;
- Everyone sings at the same time, and the mixture is the original signal.
What the Fourier series does is to “hear how loudly and when each singer in the choir sings.”
3.5 Limitations of Fourier series
Fourier series only works forperiodic signal。
But most signals in reality are not periodic:
- What you say will not be repeated;
- An earthquake does not occur periodically;
- A pulse occurs only once.
what to do? The Fourier transform is the answer.
Four: Fourier transform (FT) – the method of disassembling any signal
4.1 A clever idea: extend the period to infinity
The Fourier series requires that the signal “repeat”.
But if a signal appears only once, we can consider its “repetition period to be infinite.”
周期 = 1 秒： [信号][信号][信号][信号]...
周期 = 10 秒： [信号..............][信号..............]...
周期 = 无穷大： [信号........................................]
（只出现一次，再也不重复）
When the period approaches infinity, the Fourier series “evolves” intoFourier Transform。
4.2 From “discrete frequency” to “continuous frequency”
This is the most crucial difference.
Fourier series: Frequency is a column, only in \((f, 2f, 3f, \dots)\) These places have value.
傅里叶级数频谱：
█
█ █
█ █ █
────┴───┴───┴────> 频率
f 2f 3f
Fourier transform: The frequency is a continuous piece, and each frequency may have a little bit.
傅里叶变换频谱：
██
████
██████
████████
─────────────────> 频率
（连续的曲线）
To put it figuratively:
- The Fourier series is like a “piano”: only a few fixed keys can play;
- The Fourier transform is like a “violin”: any pitch can be played.
4.3 What is the Fourier transform asking?
Fourier transform pairevery possible frequencyAll ask one question:
“How much does your frequency account for in the original signal?”
Then give two answers:
- How big is the portion(magnitude);
- where is the starting point(Phase).
So the output of the Fourier transform, isa function of frequency：
输入：时间 → 数值 （信号）
输出：频率 → 复数 （频谱）
This “complex number” is a container that holds “amplitude” and “phase” at the same time.
4.4 Image: countless tuning forks
Imagine there is in front of youInfinitely many tuning forkseach tuning fork corresponds to a frequency.
What the Fourier transform does:
- Take each tuning fork and strike it against the signal;
- If this frequency is really present in the signal, the tuning fork will “resonate” and be loud;
- If not, the tuning fork won’t move at all.
Try it again for each frequency and you get the complete spectrum.
This is the most vivid picture of Fourier transform: using infinite number of tuning forks to detect the frequencies in the signal.
4.5 The “prism” version of the Fourier transform
Back to the prism metaphor:
graph TD
a[白光（复杂信号）]–>b[三棱镜（傅里叶变换）]
b–>c[七色光（频谱）：
红：多亮？
橙：多亮？
黄：多亮？
…]
The Fourier transform is that prism.
4.6 Two directions of Fourier transform
The Fourier transform has two directions and is very important:
forward transformation: time → frequency
“What frequencies are in this sound?”
Inverse transformation: frequency → time
“If I add these frequencies to this spectrum, what sound will I get?”
Forward transformation is “splitting”, and inverse transformation is “putting together”.
graph LR
a[信号]–>b[正变换]
b–>c[频谱]
graph RL
c[频谱]–>b[逆变换]
b–>a[信号]
Both directions are important. Forward transformation is used for “analysis” and inverse transformation is used for “synthesis”.
Five: Discrete Fourier Transform (DFT) – the computer version
5.1 The Dilemma of Computers
Fourier transform is used for “continuous signals”.
But the computer only knowsdiscrete numbers。
连续信号（模拟）： ～～～～～～～～～～
（每个瞬间都有值）
离散信号（数字）： ● ● ● ● ●
（只记录了几个点）
Therefore, to move the Fourier transform into a computer, two things must be done:
- time discretization: Only take a limited number of sampling points;
- frequency discretization: Only a limited number of frequencies are counted.
this is Discrete Fourier Transform。
5.2 Three “discrete” aspects of DFT
| project | Continuous Fourier Transform | DFT |
|---|---|---|
| time | continuous | Discrete (N points) |
| frequency | continuous | Discrete (N frequencies) |
| calculate | integral | Sum |
DFT is to replace “integration” with “sum”.
Integration is “accumulating continuously”, and summation is “adding up one by one”.
Computers only know the latter.
5.3 DFT screen:\(N\) tuning forks in a row
Imagine there is in front of you \(N\) tuning forklined up in a row, corresponding to \(N\) frequency:
音叉0 音叉1 音叉2 ... 音叉N-1
│ │ │ │
f0 f1 f2 fN-1
You have it in your hand \(N\) sampling points：
● ● ● ● ● ● ● ●
x0 x1 x2 x3 x4 x5 x6 x7
What DFT does:
- tuning fork \(0\),and \(N\) The sampling points are “compared” one by one and added up;
- tuning fork \(1\),repeat;
- …
- tuning fork \(N – 1\),repeat.
Each tuning fork gives a result.\(N\) tuning fork given \(N\) results.
That’s what DFT is all about.
5.4 How does “comparison” work?
This is the easiest place to get confused. Say it carefully.
Each tuning fork corresponds to a frequency. This frequency has its own “standard waveform”:
音叉 k 的标准波形：一个会转圈的指针
Concrete phrase, tuning fork \(k\) The standard waveform is “every time a sampling point is taken, the pointer rotates \(\frac{k}{N}\) lock up”.
音叉 0：每步转 0 圈 （原地不动）
音叉 1：每步转 1/N 圈
音叉 2：每步转 2/N 圈
...
音叉 N/2：每步转半圈 （正负交替）
...
Comparison method:
- The signal is in the \(n\) points, multiplied by the tuning fork \(k\) In the first \(n\) Step pointer position;
- put all \(n\) The products add up.
If the signal is “in tune” with this tuning fork, the products will add up in the same direction, and the sum will be very large;
If they are not in tune, the products will cancel out positively and negatively, and the sum will be close to \(0\)。
This is exactly the same as the previous scene of “strike with a tuning fork”.
5.5 How to read the results of DFT?
DFT output \(N\) plural number. Each complex number contains two pieces of information:
第 k 个结果 = 幅度 + 相位
│ │
│ └── 这个频率的波从哪里开始
│
└────────── 这个频率有多响
No. \(0\) This result is particularly important:
第 0 个结果 = 所有采样点的和 = 直流成分
Because its corresponding tuning fork “stays in place,” the comparison is “adding it all up.”
5.6 Symmetry of DFT: only half of the real signal counts
If the inputs are real (as real signals almost always are), the DFT has a nice symmetry:
第 k 个结果 和 第 N-k 个结果，是“共轭”关系
（幅度相同，相位相反）
means:
频谱的前一半和后一半，是镜像的
Therefore, in practice, only the first half is often counted (\(0\) arrive \(\frac{N}{2}\)), saving half the workload.
To put it figuratively: The spectrum of a real signal is like a butterfly, symmetrical from left to right. You just have to look aside.
5.7 The fatal problem of DFT: too slow
DFT calculation amount:
- \(N\) sampling points;
- \(N\) frequency;
- To be done for each frequency \(N\) times multiplication and addition.
Total:\(N \times N = N^2\) operations.
| \(N\) | \(N^2\) | Intuitive feeling |
|---|---|---|
| \(8\) | \(64\) | moment |
| \(1024\) | about \(100\) Ten thousand | a moment |
| \(100\) Ten thousand | \(1\) trillions | Until the end of time |
\(N\) If it is slightly larger, the DFT will not move. This is why FFT comes into play.
Six: Fast Fourier Transform (FFT) – Let DFT fly
6.1 FFT (Fast Fourier Transform) is not a new transformation
FFT is not a new transformation. The result it calculates is exactly the same as DFT.
FFT is justA faster algorithm for calculating DFT。
6.2 Core findings of FFT: duplication of effort
In DFT, each frequency must be multiplied by each sampling point.
But look carefully, many multiplications areDuplicate。
Specifically, the “pointers” used by DFT have an important property:
指针转一圈，回到原地
指针转半圈，方向相反
This means:
- tuning fork \(k\) chord fork \(k+N\) The pointer positions are exactly the same;
- tuning fork \(k\) chord fork \(k+\frac{N}{2}\) The pointer position is exactly the opposite.
These duplicates can be merged.
6.3 A stroke of genius: split according to odd and even numbers
The core operations of FFT are incredibly simple: Divide the sampling points into two teams according to the odd and even numbers.
原始： x0 x1 x2 x3 x4 x5 x6 x7
偶数队：x0 x2 x4 x6
奇数队： x1 x3 x5 x7
Then:
- The even-numbered team calculates the DFT (length \(\frac{N}{2}\)）；
- The odd-numbered team calculates a DFT (length \(\frac{N}{2}\)）；
- Combine the two results into \(N\) results.
Original question:\(N\) A count \(N\) frequency.
After disassembly: two \(\frac{N}{2}\) Click the question and finally merge it.
this isdivide and conquer。
6.4 Why is splitting by odd-even possible?
DFT village, tuning fork \(k\) The pointer “turns each step” \(\frac{k}{N}\) lock up”.
Now look at the even numbered positions \(（0, 2, 4, 6）\) and odd positions \(（1, 3, 5, 7）\)：
偶数位置：指针走了 0 步、2 步、4 步、6 步
奇数位置：指针走了 1 步、3 步、5 步、7 步
At the even-numbered position, the pointer actually “turns every step” \(\frac{2k}{N}\) lock up”.
This is exactly the “length \(\frac{N}{2}\) DFT” uses the pointer speed (because \(\frac{2k}{N} = \frac{k}{\frac{N}{2}}\))）。
Therefore, the DFT at even-numbered positions is a length \(\frac{N}{2}\) DFT.
The same applies to odd-numbered positions.
This is the mathematical reason why “split” can be established: two steps of the pointer are equal to one step of the small pointer.
6.5 The secret to merging: the butterfly
Now combine the results of the two small DFTs.
Calculate by assuming an even number of teams \(E\)the odd-numbered team calculates \(O\)。
to get original \(N\) For point results, you need to do:
\[上结果 = E + (指针方向 × O)\\
\\
下结果 = E – (指针方向 × O)
\]
The shape is like a butterfly, so it is called butterfly arithmetic.
Three key points:
- a multiplication: Counts only once”\(Pointer direction\times O\)”；
- two outputs: Add once, subtract once;
- complementary up and down: When the pointer rotates half a circle, the up and down results are interchanged.
This is the core of FFT’s time saving: one multiplication, feeding two results.
6.6 Build it up layer by layer
It is not enough to dismantle it once, it must be dismantled to a single point:
graph TD
a[8 点]–>b[偶数 4 点]
b–>d[偶偶 2 点]
b–>e[偶奇 2 点]
d–>f[1 点]
d–>g[1 点]
e–>h[1 点]
e–>i[1 点]
a–>c[奇数 4 点]
c–>j[奇偶 2 点]
c–>k[奇奇 2 点]
j–>l[1 点]
j–>m[1 点]
k–>n[1 点]
k–>o[1 点]
\(1\) The DFT of a point is itself. This is the end of the disassembly step.
Then merge from bottom to top:
第 1 层：每 2 个点合并
第 2 层：每 4 个点合并
第 3 层：每 8 个点合并
Number of layers \(=\) \(N\) continuous division by \(2\) how many times to arrive \(1\),Right now \(log(N)\)。
6.7 Seat rearrangement: bit inversion
When splitting according to odd and even, the order of leaves will be messed up in the end.
In order to “not recurse and directly iterate” in the program, the input needs to be rearranged from the beginning.
Reordering rules:Write the number in binary and read it backwards.
0 (000) → 000 → 0
1 (001) → 100 → 4
2 (010) → 010 → 2
3 (011) → 110 → 6
4 (100) → 001 → 1
5 (101) → 101 → 5
6 (110) → 011 → 3
7 (111) → 111 → 7
New order:
0, 4, 2, 6, 1, 5, 3, 7
This is what the “swapping seats” lines at the beginning of the FFT program do.
6.8 Complete process (\(8\) Click as an example)
graph TD
a[输入：
x0 x1 x2 x3 x4 x5 x6 x7]–>b[位反转重排
x0 x4 x2 x6 x1 x5 x3 x7]
b–>c[第 1 层：相邻两两蝶形
● ● ● ● ● ● ● ●]
c–>d[第 2 层：每 4 个一组蝶形
●───────●●───────●]
d–>e[第 3 层：整体蝶形
●───────────────●]
e–>f[输出：
x0 x1 x2 x3 x4 x5 x6 x7]
6.9 A specific example: all 1 signals
enter:
1 1 1 1 1 1 1 1
Tier 1(Two adjacent butterflies, pointers in place):
1+1=2, 1-1=0 → 2 0 2 0 2 0 2 0
Tier 2(per group of 4):
前半 2 0 和 2 0： 上=4，下=0；另一对 O=0，所以都是 2
得到：4 2 0 2
后半同理：4 2 0 2
合起来：4 2 0 2 4 2 0 2
Tier 3(overall):
前半和后半完全一样，所以：
4+4=8，4-4=0，其余同理
得到：8 0 0 0 0 0 0 0
result:
第 0 个 = 8 （直流，所有点加起来）
其余 = 0 （没有其他频率）
Completely intuitive: all \(1\) The constant signal is DC only.
6.9 Speed improvements
| \(N\) | \(N\space log\space N\) | Intuitive feeling |
|---|---|---|
| \(8\) | \(24\) | moment |
| \(1024\) | \(10240\) | moment |
| \(100\) Ten thousand | about \(2000\) Ten thousand | soon |
Seven: General diagram of the relationship between the four
Now string the entire path together:
graph TD
a[傅里叶级数（周期信号）
频率离散
用和式表示]–Period$\infty$–>b[傅里叶变换
（任意信号）
频率连续
用积分表示]
b–Time and frequency are both discrete–>c[DFT（计算机版本）
时间离散
频率离散
用求和表示]
c–Accelerate with divide and conquer–>d[FFT（DFT 的快速算法）
结果和 DFT 相同
复杂度 $N\space log\space N$]
Put it together in one sentence:
Harmonic analysis is the knowledge of “breaking waves”; Fourier series breaks down periodic signals; Fourier transform breaks down arbitrary signals; DFT is a discrete version that computers can calculate; FFT is a fast algorithm of DFT.
Eight: The last word
If you can only remember one sentence from the entire explanation, please remember this:
Fourier transform is the prism of mathematics, which splits complex signals into simple waves; DFT is a discrete version for computers; FFT is a divide-and-conquer algorithm that changes DFT from “cannot be calculated” to “calculated in seconds”.
Then simplify it into three actions:
graph LR
a[拆（按奇偶分）]–>b[转（指针方向）]
b–>c[合（蝶形加减）]
These three actions are the entire soul of FFT.
And FFT is just the most practical branch on the big tree of harmonious analysis.
I wish you go from “newbie” to “can realize FFT by yourself”.
Give it a thumbs up:
Attached:
Statement: The author’s school invited Professor Joshua Zar to explain “Harmonic Analysis and Fourier Transform” (teaching in English, I didn’t quite understand it). In order to consolidate and expand relevant knowledge, the author asked deepseek to generate this content. The content generated by deepseek was difficult to understand. I spent half a day processing it, such as adding some content to make the article more understandable. All flowcharts, formulas, pictures, etc. were added by me in a time-consuming and laborious manner.
Let me reiterate: I used AI because the author didn’t understand. Let AI explain. If you don’t like it, don’t criticize.
It is not easy to make, please understand. If there is anything you think is incorrect or inappropriate, please leave a message in the comment area to correct it in time. Thank you!
If you find it helpful, please give it a like! (❁´◡`❁)
