我的 “基2-快速傅立葉變換” 的樸素實(shí)現(xiàn)（推導(dǎo)部分）

本篇目的：

1）回顧一下基2-快速傅立葉變換（radix2-FFT）的理論推導(dǎo)；

2）以C++語(yǔ)言用最直白的方式實(shí)現(xiàn) 基2-快速傅立葉變換踱阿。

例行推導(dǎo)

我們考慮的 基 2-FFT 需要數(shù)據(jù)長(zhǎng)度為? $2^m$ ?形式管钳，其中? $m \in \mathbb N$ 。

離散傅立葉變換 DFT 公式如下：

$X(k) = \sum_{n=1}^{N-1} x(n) W_{N}^{kn}\ , \ k=0,1,...,N-1$

其中： $W_{N} = e^{-j2\pi/N}$ 為 1 的 $N$ 次單位根软舌；計(jì)算這 $N$ 個(gè)變換系數(shù) $X(k)$ 需要? $N^2$ ?次復(fù)數(shù)乘法才漆，和 $N(N-1)$ 次復(fù)數(shù)加法。為了得到一個(gè)高效的算法佛点，我們作出以下變換栽烂。

$\begin{aligned}X(k) &= \sum_{n=1}^{N-1} x(n) W_{N}^{kn}\ \ , \ k=0,1,...,N-1 \\&= \underbrace{ \sum_{n=1}^{N/2-1} x(2n) W_{N}^{k2n} }_{\text {even items}} + \underbrace{ \sum_{n=1}^{N/2-1} x(2n+1) W_{N}^{k(2n+1)} }_{\text {odd items}}\ \ , \ k=0,1,...,N-1 \\&= \sum_{n=1}^{N/2-1} x(2n) W_{N/2}^{kn} + W_{N}^k\sum_{n=1}^{N/2-1} x(2n+1) W_{N/2}^{kn} \ \ , \ k=0,1,...,N-1 \\\end{aligned} \quad \cdots (1)$

其中：我們用到了 $W_{N}^{2n} := e^{-j2\pi 2n/N} = e^{-j2\pi n/(N/2)} := W_{N/2}^{n}$

????????到此，DFT 運(yùn)算的復(fù)數(shù)乘法量不減反增恋脚；不過(guò)這里蘊(yùn)含的“重復(fù)計(jì)算”不是一眼就能看出來(lái)的腺办，找到這樣的”重復(fù)計(jì)算“就是快速傅立葉變換的核心所在。下面我們將利用 旋轉(zhuǎn)因子? $W_N^{n}$ ?的以下特殊性質(zhì)糟描，找到重復(fù)的乘法運(yùn)算怀喉，并將其優(yōu)化掉：

1）周期性： $W_N^{l+N} = e^{-j2\pi(l+N)}=e^{-j2\pi l}e^{-j2\pi N} =e^{-j2\pi l} = W_N^{l}$

2）斜對(duì)稱(chēng)性： $W_N^{l+N/2} = e^{-j2\pi(l+N/2)/N}=e^{-j2\pi l/N}e^{-j\pi} =-e^{-j2\pi l} = -W_N^{l}$

????????如果我們?cè)谏希?）式中，將? $k$ ?的取值范圍限制為 $\mathbb Z \cap [0\ ,\ N/2-1]$ 船响，則（1）式中的奇偶部分可以分別視為?奇數(shù)下標(biāo)子序列和偶數(shù)下標(biāo)子序列的長(zhǎng)度均為? $N/2$ ?的 DFT 躬拢。令 $y(n) = x(2n)$ ， $z(n) = x(2n+1)$ 见间， $n \in \mathbb Z \cap [0 \ , \ N/2-1]$ 聊闯，得到子序列的 DFT：

$\begin{aligned} A(k) &= \sum_{n=1}^{N/2-1} y(n) W_{N/2}^{kn} \ \ ,\ \ k=0,1,...,N/2-1 \\B(k) &= \sum_{n=1}^{N/2-1} z(n) W_{N/2}^{kn} \ \ , \ k=0,1,...,N/2-1 \\\end{aligned}$

于是完整序列的 DFT 的前半部分系數(shù)可以表示如下：

$\begin{aligned}X(k) &= A(k) + W_{N}^k B(k) \ \ ,\ \ k=0,1,...,N/2-1\end{aligned}$

下面計(jì)算完整序列的 DFT 的后半部分系數(shù)? $X(k+N/2)\ , \ k=0,1,...,N/2$ ；為了清晰米诉，我們重新算一遍：

$\begin{aligned}X(k+N/2) &= \sum_{n=1}^{N-1} x(n) W_{N}^{(k+N/2)n}\ \ , \ k=0,1,...,N/2-1 \\&= \sum_{n=1}^{N/2-1} x(2n) W_{N}^{(k+N/2)2n} + \sum_{n=1}^{N/2-1} x(2n+1) W_{N}^{(k+N/2)(2n+1)} \ \ , \ k=0,1,...,N/2-1 \\&= W_N^{nN}\sum_{n=1}^{N/2-1} x(2n) W_{N/2}^{kn} + W_N^{Nn+N/2+k}\sum_{n=1}^{N/2-1} x(2n+1) W_{N/2}^{kn} \ \ , \ k=0,1,...,N/2-1 \\&= \sum_{n=1}^{N/2-1} x(2n) W_{N/2}^{kn} - W_N^{k}\sum_{n=1}^{N/2-1} x(2n+1) W_{N/2}^{kn} \ \ , \ k=0,1,...,N/2-1 \\&= A(k) - W_N^k B(k)\end{aligned}$

到此菱蔬，我們得到了最重要的結(jié)果：

$\begin{cases}X(k) &= A(k) + W_N^k B(k)\\X(k+N/2) &= A(k) - W_N^kB(k)\end{cases} \quad , \quad k=0,...,N/2 -1 \quad \cdots (2)$

????????而這就是著名的 蝶形運(yùn)算 ，可以看到我們只用了一次復(fù)數(shù)乘法（兩次加法）史侣，就得到了兩個(gè) DFT 系數(shù)拴泌，而這也是 FFT 的核心。在上（2）式中惊橱，如果使用樸素方法直接計(jì)算 $A(k), B(k), k=0,...,N/2-1$ 蚪腐，則共需要 $(N/2)^2 \times 2 + N/2$ ?次復(fù)數(shù)乘法運(yùn)算。所以税朴，經(jīng)過(guò)一次奇偶拆分回季，我們直接將計(jì)算復(fù)雜度降低了約一半家制。

? ? ? ? 在我們的約定下 $N=2^m$ ，于是當(dāng)我們想要計(jì)算 $A(k),B(k),k=0,...,N/2-1$ 時(shí)泡一，我們不妨繼續(xù)對(duì) $y(n),z(n),n=0,...,N/2-1$ 分別進(jìn)行奇偶拆分慰丛，這樣的拆分過(guò)程在 DSP 領(lǐng)域有個(gè)專(zhuān)門(mén)的術(shù)語(yǔ)叫 Decimation In Time（DIT）。這樣的過(guò)程可以進(jìn)行? $m$ ?次瘾杭，于是我們就得到了 radix2-DIT-FFT 算法過(guò)程诅病。顯然，每一層我們只需要? $N/2$ ?次復(fù)數(shù)乘法粥烁，共 $\log N$ 層贤笆，于是復(fù)數(shù)乘法量降低為 $\frac{N}{2}\log N$ 。

? ? ? ? 實(shí)現(xiàn)這個(gè)過(guò)程有兩種方法：1）使用 遞歸法 逐層對(duì)序列進(jìn)行奇偶抽忍肿琛芥永；2）使用 迭代法 從最底層前向推進(jìn)。我們嘗試使用迭代法來(lái)實(shí)現(xiàn)代碼钝吮，不過(guò)在這之前埋涧，我們還需要分析在每層中數(shù)據(jù)的排列；如下圖（1）奇瘦，對(duì)于一個(gè) 8 點(diǎn) FFT 我們會(huì)有 3 層抽取過(guò)程棘催，最終的數(shù)據(jù)排列為 0,4,2,6,1,5,3,7；那么如何在實(shí)際中確定長(zhǎng)度為 N 的樣本點(diǎn)的排列順序呢耳标？偉大的前人發(fā)現(xiàn)當(dāng)我們把 下標(biāo) 按 2 進(jìn)制進(jìn)行展開(kāi)時(shí)醇坝，則重排的序列中每個(gè)元素的下標(biāo)剛好就是該元素在原來(lái)序列中的下標(biāo) 按位逆序 得到（如下圖 2 ）。

圖1）DIT 逐層抽取過(guò)程

圖2）按位逆序的對(duì)應(yīng)關(guān)系

矩陣運(yùn)算視角

例如當(dāng) $N=8$ 時(shí)次坡，我們可以使用 $8\times 8$ 的線性變換來(lái)表示：

$\left [ \begin{array}{} X(0) \\ X(1) \\ \ \ \vdots \\ X(7) \end{array} \right] = \left [ \begin{array}{} W_{8}^{0\times 0} & W_{8}^{0\times 1} & \cdots & W_{8}^{0\times 7} \\ W_{8}^{1\times 0} & W_{8}^{1 \times 1} & \cdots & W_{8}^{1\times 7} \\ \vdots & \vdots & \ddots & \vdots \\ W_{8}^{7\times 0} & W_{8}^{7 \times 1} & \cdots & W_{8}^{7 \times 7} \end{array} \right ] \left [ \begin{array}{} x(0) \\ x(1) \\ \vdots \\ x(7) \end{array} \right ] \quad \cdots (1)$

我們把中間的矩陣詳細(xì)寫(xiě)開(kāi)：

$F= \left [ \begin{array}{} 1 & 1 & 1 & 1 & 1 & 1& 1& 1 \\ 1 & W_{8}^{1} & W_{8}^{2} & W_{8}^{3} &W_{8}^{4} & W_{8}^{5} & W_{8}^{6}& W_{8}^{7} \\ 1 & W_{8}^{2} & W_{8}^{4} & W_{8}^{6} &W_{8}^{8} & W_{8}^{10} & W_{8}^{12}& W_{8}^{14} \\ 1 & W_{8}^{3} & W_{8}^{6} & W_{8}^{9} &W_{8}^{12} & W_{8}^{15} & W_{8}^{18}& W_{8}^{21} \\ 1 & W_{8}^{4} & W_{8}^{8} & W_{8}^{12} &W_{8}^{16} & W_{8}^{20} & W_{8}^{24}& W_{8}^{28} \\ 1 & W_{8}^{5} & W_{8}^{10} & W_{8}^{15} &W_{8}^{20} & W_{8}^{25} & W_{8}^{30}& W_{8}^{35} \\ 1 & W_{8}^{6} & W_{8}^{12} & W_{8}^{18} &W_{8}^{24} & W_{8}^{30} & W_{8}^{36}& W_{8}^{42}\\ 1 & W_{8}^{7} & W_{8}^{14} & W_{8}^{21} &W_{8}^{28} & W_{8}^{35} & W_{8}^{42}& W_{8}^{49} \end{array} \right ]$

再次由周期性?和斜對(duì)稱(chēng)性呼猪，我們來(lái)對(duì)上面的矩陣作一些化簡(jiǎn)：

$F= \left [ \begin{array}{} 1 & 1 & 1 & 1 & 1 & 1& 1& 1 \\ 1 & W_{8}^{1} & W_{8}^{2} & W_{8}^{3} &-1 & -W_{8}^{1} & -W_{8}^{2}& -W_{8}^{3} \\ 1 & W_{8}^{2} & -1 & -W_{8}^{2} & 1 & W_{8}^{2} & -1 & -W_{8}^{2} \\ 1 & W_{8}^{3} & -W_{8}^{2} & W_{8}^{1} & -1 & -W_{8}^{3} & W_{8}^{2}& -W_{8}^{1} \\ 1 & -1 & 1 & -1 &1 & -1 & 1& -1\\ 1 & -W_{8}^{1} & W_{8}^{2} & -W_{8}^{3} &-1 & W_{8}^{1} & -W_{8}^{2}& W_{8}^{3} \\ 1 & -W_{8}^{2} & -1 & W_{8}^{2} & 1 & -W_{8}^{2} & -1& W_{8}^{2}\\ 1 & -W_{8}^{3} & -W_{8}^{2} & -W_{8}^{1} &-1 & W_{8}^{3} & W_{8}^{2}& W_{8}^{1} \end{array} \right ]$

? ? ? ? 暫時(shí)，讓我們忘掉前面的 例行推導(dǎo)?的結(jié)論砸琅，重新用矩陣乘法視角來(lái)看看傅立葉變換過(guò)程宋距。

????????我們注意到該矩陣內(nèi)部包含了大量的重復(fù)元素，那么是否可以利用這一現(xiàn)象減少一些“重復(fù)計(jì)算“呢症脂？前面已經(jīng)給出了肯定的答案谚赎；我們繼續(xù)以”事后諸葛亮“的視角分析一下矩陣 $F$ 。

? ? ? ? 我們把（1）式記為向量符號(hào)形式： ${\rm X} = F \boldsymbol x$ 摊腋，設(shè) $P$ 為任意置換矩陣沸版，由線性代數(shù)知識(shí)可知：其右乘矩陣相當(dāng)于對(duì)矩陣的列向量作相應(yīng)的排列，左乘一個(gè)矩陣相當(dāng)于對(duì)矩陣的行向量作相應(yīng)的排列兴蒸；并且將置換矩陣 $P$ ?兩次?右乘到矩陣? $F$ ?相當(dāng)于對(duì)列向量換過(guò)去又換回來(lái)，也就是 $PP = I$ 细办，于是我們得到：

${\rm X} = F I \boldsymbol x = F(PP)\boldsymbol x=(FP)(P\boldsymbol x)$

? ? ? ? 下面我們令? $P_8$ ?是由單位矩陣? $I_8$ ?經(jīng)過(guò)如下變換得到的矩陣：交換? $I_8$ ?的第 1 行和第 4 行橙凳，交換第 3 行和第 6 行蕾殴。至于為什么矩陣? $P_8$ ?是這樣的，因?yàn)槲艺f(shuō)過(guò)這是 “事后諸葛亮”岛啸，其實(shí)這就是 “按位逆序法 bit reversing order” 得到的钓觉。如此得到下面的按列向量重排過(guò)的矩陣? $F_{br}$ ，當(dāng)然數(shù)據(jù)向量? $\boldsymbol x$ ?的行也按同樣的規(guī)律重排過(guò)了坚踩。

$F_{br}= \left [ \begin{array}{c0,c1,c2,c3,|c4c5,c6,c7} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 &-1 & W_{8}^{2} &-W_{8}^{2} & W_{8}^{1} &-W_{8}^{1} & W_{8}^{3} &-W_{8}^{3} \\ 1 & 1 & -1 &-1 & W_{8}^{2} & W_{8}^{2} &-W_{8}^{2} &-W_{8}^{2} \\ 1 &-1 & -W_{8}^{2} & W_{8}^{2} & W_{8}^{3} &-W_{8}^{3} & W_{8}^{1} &-W_{8}^{1} \\\hline 1 & 1 & 1 & 1 &-1 &-1 &-1 &-1\\ 1 &-1 & W_{8}^{2} & -W_{8}^{2} &-W_{8}^{1} & W_{8}^{1} &-W_{8}^{3} & W_{8}^{3} \\ 1 & 1 & -1 & -1 &-W_{8}^{2} &-W_{8}^{2} & W_{8}^{2} & W_{8}^{2}\\ 1 &-1 & -W_{8}^{2} & W_{8}^{2} &-W_{8}^{3} & W_{8}^{3} &-W_{8}^{1} & W_{8}^{1} \end{array} \right ] =\left [ \begin{array}{}F_{00} & F_{01}\\F_{10} &F_{11}\end{array} \right ]$

? ? ? ? 其中： $F_{br} = FP_8$ 荡灾，觀察該分塊矩陣，我們發(fā)現(xiàn)：

1） $F_{00} = F_{10}$ 瞬铸；

2） $F_{01}$ 的每一列由 $F_{00}$ 的對(duì)應(yīng)的列乘以對(duì)應(yīng)的因子 $W_{8}^{n} \ ,\ n=0,1,2,3$ 得到的批幌；

3） $F_{11}$ 的每一列由 $F_{00}$ 的對(duì)應(yīng)的列?乘以對(duì)應(yīng)的因子 $-W_{8}^{n}\ , \ n=0,1,2,3$ 得到的；

? ? ? ? 簡(jiǎn)化一下符號(hào)嗓节，設(shè) $F_4 = F_{00}\ ,\ A=\left [ \begin{array}{} 1 & & & \\ &W_{8}^{1} &&\\&&W_{8}^{2} &\\&&&W_{8}^{3} \end{array} \right ]$ 荧缘；用矩陣語(yǔ)言來(lái)表達(dá)上面的描述，如下：

$\begin{aligned}F_{br}&=\left [ \begin{array}{}F_4 & AF_4\\F_4 &-AF_4\end{array} \right ] \\&=\left [ \begin{array}{} I_4 & A\\I_4 &-A\end{array} \right ] \left [ \begin{array}{} F_4 & \\ &F_4\end{array} \right ] \\&=\left [ \begin{array}{} I_4 & I_4\\I_4 &-I_4\end{array} \right ] \left [ \begin{array}{} I_4 & \\ &A \end{array} \right ] \left [ \begin{array}{} F_4 & \\ &F_4\end{array} \right ]\end{aligned} \quad \cdots (2)$

同理拦宣，記： $F_{4}= \left [ \begin{array}{c0,c1|c2,c3} 1 & 1 & 1 & 1 \\ 1 &-1 & W_{8}^{2} &-W_{8}^{2} \\ \hline 1 & 1 & -1 &-1 \\ 1 &-1 & -W_{8}^{2} & W_{8}^{2} \\ \end{array} \right ] = \left [ \begin{array}{}F_2 & BF_2 \\F_2 &-BF_2 \end{array} \right ]$

其中： $F_2= \left [ \begin{array}{}1 & \ \ \ 1 \\1 &-1 \end{array} \right ]$ 截粗， $B= \left [ \begin{array}{}1 & \\ & W_8^2 \end{array} \right ]$

繼續(xù)作分解：

$\begin{aligned} F_{4} &= \left [ \begin{array}{}F_2 & BF_2 \\F_2 &-BF_2 \end{array} \right ] \\&= \left [ \begin{array}{}I_2 & B \\I_2 &-B \end{array} \right ] \left [ \begin{array}{}F_2 & \\ &F_2 \end{array} \right ] \\&= \underbrace{\left [ \begin{array}{}I_2 & I_2 \\I_2 &-I_2 \end{array} \right ] }_C \underbrace{\left [ \begin{array}{}I_2 & \\ &B \end{array} \right ] }_D\underbrace{ \left [ \begin{array}{}F_2 & \\ &F_2 \end{array} \right ] }_G \\\end{aligned}$

再次，利用 分塊對(duì)角矩陣 乘法的便利性鸵隧，得到：

$\left [ \begin{array}{} F_4 & \\ &F_4\end{array} \right ]=\left [ \begin{array}{} CDG & \\ &CDG\end{array} \right ] = \left [ \begin{array}{} C & \\ &C\end{array} \right ]\left [ \begin{array}{} D & \\ &D\end{array} \right ]\left [ \begin{array}{} G & \\ &G\end{array} \right ]$

代入上面（2）式中得：

$\begin{aligned}F_{br} &=\left [ \begin{array}{} I_4 & I_4\\I_4 &-I_4\end{array} \right ] \left [ \begin{array}{} I_4 & \\ &A \end{array} \right ] \left [ \begin{array}{} C & \\ &C\end{array} \right ]\left [ \begin{array}{} D & \\ &D\end{array} \right ]\left [ \begin{array}{} G & \\ &G\end{array} \right ]\end{aligned}$

將 $A,B,C,D,G$ 代入上式整理后得到：

$F_{br} = \underbrace{ \left [ \begin{array}{} I_4 & I_4\\I_4 &-I_4\end{array} \right ] }_{E}\underbrace{ \left [ \begin{array}{c0,c1,c2,c3|c4,c5,c6,c7}1&&&&&&& \\&1&&&&&& \\&&1&&&&& \\&&&1&&&& \\\hline&&&& 1 & & & \\&&&& &W_{8}^{1} &&\\&&&&&&W_{8}^{2} &\\&&&&&&&W_{8}^{3} \end{array} \right ] }_{D}\underbrace { \left [ \begin{array}{c0,c1,|c2,c3}I_2&\ \ \ I_2 && \\I_2&-I_2 && \\\hline& &I_2 &\ \ \ I_2 \\& &I_2 &-I_2 \end{array} \right ] }_{C}\underbrace{\left [ \begin{array}{c0,c1,c2,c3|,c4,c5,c6,c7} 1&&&&&&& \\ &1&&&&&& \\ &&1&&&&& \\ &&&W_8^2&&&& \\\hline &&&&1&&& \\ &&&&&1&& \\ &&&&&&1& \\ &&&&&&&W_8^2 \end{array} \right ]}_{B}\underbrace{\left [ \begin{array}{c0,c1|,c2,c3|,c4,c5|,c6,c7} 1 &\ \ \ 1 & & & & & &\\ 1 &-1 & &&&&& \\\hline & &1 &\ \ \ 1 & &&& \\ & &1 &-1 & &&& \\\hline & & & &1 &\ \ \ 1 && \\ & & & &1 &-1 && \\\hline & & & & & &1 &\ \ \ 1\\ &&&&&&1&-1\end{array} \right ] }_{A}$

其中： $I_2\ ,\ I_4$ 分別為 2 階和 4 階單位矩陣凿掂，限于空間和美觀度，這里就不展開(kāi)了舀凛；并且我們將上面的矩陣從右到左依次命令為 $A,B,C,D,E$ 种蝶。

? ? ? ? 將上面的展開(kāi)式左乘置換后的數(shù)據(jù)向量? $\tilde{\boldsymbol x}$ ?，我們就得到了快速傅立葉變換的過(guò)程靡羡；我們將上面的展開(kāi)式中的矩陣系洛，依次從右到左用流程圖畫(huà)出來(lái)，就得到下面的變換圖：（其中W^n 表示 $W_8^n$ 略步，沒(méi)有明確寫(xiě)出來(lái)的權(quán)重均為 1）

圖3）radix2 FFT 流圖

由于簡(jiǎn)書(shū)平臺(tái) 的富文本格式不能同時(shí)支持“Latex符號(hào)”和“代碼塊嵌入”描扯，所以我將 C++ 的實(shí)現(xiàn)放到?下一篇?中。

最后編輯于：2023.01.13 11:15:58

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

禁止轉(zhuǎn)載趟薄，如需轉(zhuǎn)載請(qǐng)通過(guò)簡(jiǎn)信或評(píng)論聯(lián)系作者绽诚。

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市杭煎，隨后出現(xiàn)的幾起案子恩够，更是在濱河造成了極大的恐慌，老刑警劉巖羡铲，帶你破解...
沈念sama閱讀 216,544評(píng)論 6贊 501
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件蜂桶，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡也切，警方通過(guò)查閱死者的電腦和手機(jī)扑媚，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,430評(píng)論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)腰湾，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人疆股，你說(shuō)我怎么就攤上這事费坊。” “怎么了旬痹？”我有些...
開(kāi)封第一講書(shū)人閱讀 162,764評(píng)論 0贊 353
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵附井，是天一觀的道長(zhǎng)。經(jīng)常有香客問(wèn)我两残，道長(zhǎng)永毅，這世上最難降的妖魔是什么？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,193評(píng)論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任磕昼，我火速辦了婚禮卷雕，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘票从。我一直安慰自己漫雕，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,216評(píng)論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布峰鄙。她就那樣靜靜地躺著浸间，像睡著了一般。火紅的嫁衣襯著肌膚如雪吟榴。梳的紋絲不亂的頭發(fā)上魁蒜，一...
開(kāi)封第一講書(shū)人閱讀 51,182評(píng)論 1贊 299
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音吩翻，去河邊找鬼兜看。笑死，一個(gè)胖子當(dāng)著我的面吹牛狭瞎，可吹牛的內(nèi)容都是我干的细移。我是一名探鬼主播，決...
沈念sama閱讀 40,063評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼熊锭，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼弧轧！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起碗殷，我...
開(kāi)封第一講書(shū)人閱讀 38,917評(píng)論 0贊 274
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤精绎，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后锌妻，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體代乃，經(jīng)...
沈念sama閱讀 45,329評(píng)論 1贊 310
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,543評(píng)論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年从祝，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了襟己。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片引谜。...
茶點(diǎn)故事閱讀 39,722評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡牍陌，死狀恐怖擎浴，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情毒涧，我是刑警寧澤贮预，帶...
沈念sama閱讀 35,425評(píng)論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站契讲，受9級(jí)特大地震影響仿吞，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜捡偏，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,019評(píng)論 3贊 326
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一唤冈、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧银伟，春花似錦你虹、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 31,671評(píng)論 0贊 22
一樁弒父案傅物，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至琉预，卻和暖如春董饰，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背圆米。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 32,825評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工卒暂，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人娄帖。一個(gè)月前我還...
沈念sama閱讀 47,729評(píng)論 2贊 368
代替公主和親
正文我出身青樓也祠，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親块茁。傳聞我的和親對(duì)象是個(gè)殘疾皇子齿坷，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,614評(píng)論 2贊 353

我的 “基2-快速傅立葉變換” 的樸素實(shí)現(xiàn)（推導(dǎo)部分）

例行推導(dǎo)

矩陣運(yùn)算視角

推薦閱讀更多精彩內(nèi)容