數(shù)字圖象處理 4 北京大學(xué)計算機研究所

1、數(shù)字圖象處理1第三節(jié) 頻域變換2.3.1 傅立葉變換導(dǎo)言理論基礎(chǔ)、連續(xù)與離散的傅立葉變換2.3.2 二維傅立葉變換特性可分離性、周期與共軛對稱、平移性、旋轉(zhuǎn)特性、線性與相似性 、均值性、拉普拉斯、卷積與相關(guān)2.3.3 快速傅立葉變換FFT算法、逆向FFT算法、算法實現(xiàn)2第三節(jié) 頻域變換2.3.1 傅立葉變換導(dǎo)言理論基礎(chǔ)連續(xù)與離散的傅立葉變換32.3.1 傅立葉變換導(dǎo)言:理論基礎(chǔ)理論基礎(chǔ)線性系統(tǒng)卷積與相關(guān)42.3.1 傅立葉變換導(dǎo)言:理論基礎(chǔ)線性系統(tǒng)系統(tǒng)的定義：接受一個輸入，并產(chǎn)生相應(yīng)輸出的任何實體。系統(tǒng)的輸入是一個或兩個變量的函數(shù)，輸出是相同變量的另一個函數(shù)。系統(tǒng)x(t)輸入y(t)輸出52.

2、3.1 傅立葉變換導(dǎo)言:理論基礎(chǔ)線性系統(tǒng)線性系統(tǒng)的定義：對于某特定系統(tǒng)，有： x1(t) y1(t) x2(t) y2(t)該系統(tǒng)是線性的當且僅當：x1(t) + x2(t) y1(t) + y2(t) 從而有：a*x1(t) a*y1(t)62.3.1 傅立葉變換導(dǎo)言:理論基礎(chǔ)線性系統(tǒng)線性系統(tǒng)移不變性的定義：對于某線性系統(tǒng)，有：x(t) y(t)當輸入信號沿時間軸平移T，有： x(t - T) y(t - T)則稱該線性系統(tǒng)具有移不變性72.3.1 傅立葉變換導(dǎo)言:理論基礎(chǔ)卷積卷積的定義離散一維卷積二維卷積的定義離散二維卷積相關(guān)的定義8第三節(jié) 頻域變換:理論基礎(chǔ)卷積的定義對于一個線性系統(tǒng)的輸

3、入f(t)和輸出h(t)，如果有一個一般表達式，來說明他們的關(guān)系，對線性系統(tǒng)的分析，將大有幫助卷積積分就是這樣的一般表達式 h(t) = g(t - )f()d 記為：h = g * f - g(t)稱為沖激響應(yīng)函數(shù)92.3.1 傅立葉變換導(dǎo)言:理論基礎(chǔ)離散一維卷積 h(i) = f(i)*g(i) = f(j)g(i-j) j二維卷積的定義 h(x,y) = f*g = f(u,v)g(x u, y v)dudv -102.3.1 傅立葉變換導(dǎo)言:理論基礎(chǔ)離散二維卷積 h(x,y) = f*g = f(m,n)g(x m, y n) m n相關(guān)的定義 h(t) = g(t + )f()d 記

4、為：y = g x -112.3.1 傅立葉變換導(dǎo)言:傅立葉變換連續(xù)與離散的傅立葉變換一維連續(xù)傅立葉變換二維連續(xù)傅立葉變換離散傅立葉變換離散傅立葉變換的計算與顯示122.3.1 傅立葉變換導(dǎo)言:傅立葉變換一維連續(xù)傅立葉變換：定義設(shè) f(x)為實變量x的連續(xù)函數(shù)， f(x)的傅立葉變換表示為Ff(x),定義為： Ff(x) = F(u) = f(x)exp(-j2ux)dx -其中 j2 = -1132.3.1 傅立葉變換導(dǎo)言:傅立葉變換一維連續(xù)傅立葉逆變換：定義如果給定F(u),f(x)可以由傅立葉逆變換得到： FF(u) = f(x) = F(u)exp(j2ux)du -其中 j2 = -

5、1142.3.1 傅立葉變換導(dǎo)言:傅立葉變換一維連續(xù)傅立葉變換：幾個概念 假設(shè)函數(shù)f(x)為實函數(shù)。但一個實函數(shù)的傅立葉變換可能為復(fù)函數(shù)：F(u) = R(u) + jI(u)（1） f(x)的傅立葉模記為： |F(u)| |F(u)| = R2(u) + I2(u)1/2（2） f(x)的傅立葉模平方記為： P(u) P(u) = |F(u)|2 = R2(u) + I2(u)152.3.1 傅立葉變換導(dǎo)言:傅立葉變換一維連續(xù)傅立葉變換：幾個概念（3） f(x)的傅立葉相位記為： (u) (u) = tan-1 (I(u) / R(u)（4） 傅立葉變換中的變量u通常稱為頻率變量 這個名稱源

6、于尤拉公式中的指數(shù)項 exp-j2ux = cos2ux - jsin2ux 如果把傅立葉變換的積分解釋為離散項的和，則易推出F(u)是一組sin和cos函數(shù)項的無限和，其中u的每個值決定了其相應(yīng)cos, sin函數(shù)對的頻率。162.3.1 傅立葉變換導(dǎo)言:傅立葉變換二維連續(xù)傅立葉變換 如果f(x,y)連續(xù)可積，并且F(u,v)可積，則存在以下傅立葉變換對，其中u,v為頻率變量： Ff(x,y)=F(u,v)=f(x,y)exp-j2(ux+vy)dxdy - FF(u,v)=f(x,y)=F(u,v)expj2(ux+vy)dudv -172.3.1 傅立葉變換導(dǎo)言:傅立葉變換二維連續(xù)傅立葉

7、變換 二維傅立葉模、相位和模平方分別為： 模： |F(u,v)| = R2(u,v) + I2(u,v)1/2 相位： (u,v) = tan-1 (I(u,v) / R(u,v) 模平方：P(u,v) = |F(u,v)|2 = R2(u,v) + I2(u,v)182.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換 假設(shè)連續(xù)函數(shù)f(x),通過取N個x單位的采樣點，被離散化為一個序列： f(x0), f(x0+x) , f(x0+2x), ,f(x0+N1 x) 無論將x作為離散的或連續(xù)的變量，在子序列中來研究都將是方便的，僅僅依賴于討論的上下文。為作到此要求定義：f(x) = f(x0+

8、 xx)192.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換 其中假設(shè)x現(xiàn)在的離散值是：0,1,2, ,N-1。 f(x0),f(x0+x),f(x0+2x), . , f(x0+N1x)表示相對與連續(xù)函數(shù)的任意N個統(tǒng)一的空間采樣202.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換函數(shù)f(x0+xx)的離散傅立葉變換對有： N-1F(u) = 1/N f(x)exp-j2ux/N x=0u = 0, 1, 2, .N-1 N-1 逆變換：f(x) = F(u)expj2ux/N u=0 x = 0, 1, 2, .N-1212.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換:二維 M

9、-1 N-1F(u,v) =1/MNf(x,y)exp-j2(ux/M+vy/N) x=0 y=0u = 0, 1, 2, M-1; v = 0, 1, 2, .N-1 M-1 N-1 f(x,y) = F(u,v)expj2(ux/M+vy/N) u=0 v=0 x = 0, 1, 2, .N-1; y = 0, 1, 2, .N-1222.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換的計算與顯示離散傅立葉變換的計算舉例離散傅立葉變換的顯示232.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換的計算舉例xf(x0)=f(x0+x)01231234242.3.1 傅立葉變換導(dǎo)言:傅立葉變

10、換F(0) = 1/4f(x)exp0= 1/4f(0) + f1(1) + f(2) + f(3)= 1/4(2 + 3 + 4 + 4)= 3.25F(1) = 1/4f(x)exp-j2x/4)= 1/4(2e0 + 3e j21/4 + 4e j22/4 + 4e j23/4)= 1/4(-2 + j)F(2) = -1/4(1 + j0)F(3) = -1/4(2 + j)252.3.1 傅立葉變換導(dǎo)言:傅立葉變換 離散傅立葉變換的計算舉例因為，函數(shù)f(x,y)的傅立葉變換是f(x,y)積分的函數(shù)因此，計算每一個傅立葉變換值，原函數(shù)f(x,y)的每一個點都需要參與262.3.1 傅立

11、葉變換導(dǎo)言:傅立葉變換離散傅立葉變換的顯示 通過對傅立葉變換模，來顯示傅立葉變換圖象。由于模的值域大于顯示的值域，因此要進行動態(tài)值域的壓縮D(u,v) = c log(1 + |F(u,v)|)其中： c = 255 / k; k = max(log(1 + |F(u,v)|)值域0,k的上限（最大值）272.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換的顯示282.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換的顯示對稱平移后29第三節(jié) 頻域變換:二維傅立葉變換特性2.3.2 二維傅立葉變換特性可分離性周期與共軛對稱平移性旋轉(zhuǎn)特性 線性與相似性 均值性 拉普拉斯 卷積與相關(guān)302.3.

12、2 二維傅立葉變換特性:可分離性可分離性二維離散傅立葉變換DFT可分離性的基本思想是： 二維DFT可分離為兩次一維DFT應(yīng)用： 二維快速傅立葉算法FFT ，是通過計算兩次一維FFT實現(xiàn)的312.3.2 二維傅立葉變換特性:可分離性可分離性的定義 M-1 N-1 F(u,v)=1/MN f(x,y)e(-j2vy/N) e(-j2ux/M) x=0 y=0u = 0, 1, 2, M-1; v = 0, 1, 2, .N-1 M-1 N-1 f(x,y)= F(u,v)e(j2vy/N) e(j2ux/M) u=0 v=0 x = 0, 1, 2, .N-1; y = 0, 1, 2, .N-1

13、322.3.2 二維傅立葉變換特性:可分離性可分離性成立的推導(dǎo)先對行（y變量）做變換： N-1F(x,v)=1/Nf(x,y)exp(-j2vy/N) y=0然后對列（x變量）進行變換： M-1F(u,v)=1/MF(x,v)exp(-j2ux/M) x=0332.3.2 二維傅立葉變換特性:可分離性先對行做變換：然后對列進行變換：f(x,y)（0，0）（N-1，M-1）xyF(x,v)（0，0）（N-1，M-1）xvF(x,v)（0，0）（N-1，M-1）xvF(u,v)（0，0）（N-1，M-1）uv342.3.2 二維傅立葉變換特性:平移性平移性定理平移性的描述函數(shù)自變量的位移的傅立葉變

14、換產(chǎn)生一個復(fù)系數(shù) Ff(x-a,y-b) = exp-j2(au+bv) F(u,v)352.3.2 二維傅立葉變換特性:平移性平移性成立的證明用一維函數(shù)為例進行證明：設(shè)位移為a,f(x-a)的傅立葉變換為： Ff(x-a) = F(u) = f(x-a)exp(-j2ux)dx -將積分乘以 1 = exp(-j2au) exp(j2au) 且設(shè)：v = x-a, dv = dx 362.3.2 二維傅立葉變換特性:平移性平移性成立的證明Ff(x-a) = F(u) = f(x-a)exp(-j2ux) exp(-j2au)exp(j2au) dx - =exp(-j2au) f(x-a)e

15、xp(-j2ux)exp(j2ua)dx - 372.3.2 二維傅立葉變換特性:平移性 = exp(-j2au) f(x-a)exp-j2u(x-a)dx - = exp(-j2au) f(v)exp-j2uvdv - = exp(-j2au)F(u)382.3.2 二維傅立葉變換特性:周期與共軛對稱周期與共軛對稱周期性的描述：離散傅立葉變換DFT和它的逆變換是以N為周期的對于一維傅立葉變換有： F(u) = F(u + N)對于二維傅立葉變換有： F(u,v) = F(u + M,v+N)392.3.2 二維傅立葉變換特性:周期與共軛對稱周期與共軛對稱共軛對稱性的描述：傅立葉變換結(jié)果是以原

16、點為中心的共軛對稱函數(shù)對于一維傅立葉變換有： F(u) = F*(-u)對于二維傅立葉變換有： F(u,v) = F*(-u ,-v)402.3.2 二維傅立葉變換特性:周期與共軛對稱共軛對稱性證明以一維傅立葉變換為例證明：F(u) =f(x)exp-j2uxdx =f(x)expj2(-u)xdx =f(x)exp-j2(-u)x*dx（取共軛復(fù)數(shù)） = F*(-u)412.3.2 二維傅立葉變換特性:旋轉(zhuǎn)特性旋轉(zhuǎn)特性旋轉(zhuǎn)特性描述：如果f(x,y)旋轉(zhuǎn)了一個角度 ，那么f(x,y)旋轉(zhuǎn)后的圖象的傅立葉變換也旋轉(zhuǎn)了相同的角度 。 設(shè)： a(x,y) = x cos() - y sin() b(

17、x,y) = x sin() + y cos()Ff(a(x,y),b(x,y) F(a(u,v),b(u,v)422.3.2 二維傅立葉變換特性:旋轉(zhuǎn)特性旋轉(zhuǎn)特性結(jié)論： 對圖像的旋轉(zhuǎn)變換和傅立葉變換的順序是可交換的FRf(x,y) RFf(x,y)432.3.2 二維傅立葉變換特性:線性與相似性線性與相似性線性的描述：傅立葉變換是線性系統(tǒng)、函數(shù)和的傅立葉變換是可分離的設(shè)：f(x,y) 的傅立葉變換為Ff(x,y)g(x,y)的傅立葉變換為Fg(x,y) 有：Ff(x,y)+g(x,y) = Ff(x,y)+Fg(x,y) 442.3.2 二維傅立葉變換特性:線性與相似性線性的證明用一維函數(shù)為

18、例進行證明：Ff(x)+g(x) = F(u) = (f(x)+g(x)exp-j2uxdx= (f(x)exp-j2ux + g(x)exp-j2ux) dx= f(x)exp-j2uxdx + g(x)exp-j2uxdx= F(u) + G(u)452.3.2 二維傅立葉變換特性:線性與相似性線性與相似性相似性的描述：a f(x,y) a F(u,v)且有： f(ax,by) 1/|ab|F(u/a,v/b) 462.3.2 二維傅立葉變換特性:線性與相似性相似性的證明用一維函數(shù)為例進行證明：f(ax) 1/|a|F(u/a) Ff(ax) = F(u) = f(ax)exp-j2uxd

19、x將指數(shù)和積分同時乘以 1 = a/a并設(shè)：v = ax, dv = adxFf(ax) = f(ax)exp-j2ux a/a a/a dx =1/a f(ax)exp-j2u xa/a adx =1/a f(v)exp-j2v (u /a) dv =1/|a|F(u/a)472.3.2 二維傅立葉變換特性:均值性均值性均值性的描述： 離散函數(shù)的均值等于該函數(shù)傅立葉變換在(0,0)點的值 M-1N-1 f(x ,y) = 1/MNf(x,y)e0 x=0 y=0f(x ,y) = F(0,0)482.3.2 二維傅立葉變換特性:拉普拉斯拉普拉斯拉普拉斯特性的描述：給出二維拉普拉斯函數(shù)的傅立葉

20、變換表達式：拉普拉斯函數(shù)：2 f(x,y) = 2f / x2 + 2f / y2其傅立葉變換為： F2 f(x,y) = -42(u2 +v2)F(u,v)這個定理將在圖象的邊界提取中用到492.3.2 二維傅立葉變換特性:卷積與相關(guān)卷積與相關(guān):空域和頻域之間的基本聯(lián)系卷積定理的描述：空域中的卷積等價于頻域中的相乘f(x,y)*g(x,y) F(u,v)G(u,v) Ff(x,y)*g(x,y) = F(u,v)G(u,v)同時有：f(x,y) g(x,y) F(u,v)*G(u,v)502.3.2 二維傅立葉變換特性:卷積與相關(guān)卷積定理成立的證明用一維函數(shù)為例進行證明： Ff(x)*g(x

21、) = f(x)*g(x) exp-j2uxdx= f(t)g(x-t)dt exp-j2uxdx 對于上面這個式子，我們可以看出是一個兩個變量t、x的二維積分。交換積分的順序有：512.3.2 二維傅立葉變換特性:卷積與相關(guān) = f(t)g(x - t) exp-2juxdxdt = f(t) g(x - t) exp-2juxdxdt將 t 視為位移量，由平移定理Gg(x - t) = g(x - t)exp-2juxdx = exp-j2tuG(u) 有： = f(t) exp-2jtuG(u) dt = G(u) f(t) exp-2jtu dt = F(u)G(u)522.3.2 二

22、維傅立葉變換特性:卷積與相關(guān)卷積與相關(guān):空域和頻域之間的基本聯(lián)系相關(guān)定理的描述： 空域中f(x,y)與g(x,y)的相關(guān)等價于頻域中F(u,v)的共軛與G(u,v) 相乘f(x,y) g(x,y) F*(u,v)G(u,v)同時有：f*(x,y) g(x,y) F(u,v)G(u,v)53第三節(jié) 頻域變換:快速傅立葉變換2.3.3 快速傅立葉變換FFT算法思想遞推公式推導(dǎo)逆向FFT算法算法實現(xiàn)542.3.3 快速傅立葉變換: FFT算法思想FFT算法基本思想 FFT算法基于一個叫做遞推加倍的方法。通過推導(dǎo)將DFT轉(zhuǎn)換成兩個遞推公式 N-1F(u)=1/N f(x) exp(-j2ux/N) x

23、=0 F(u) = 1/2(Feven(u)+Fodd(u)W2Mu) F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu) 552.3.3 快速傅立葉變換: FFT算法思想FFT算法基本思想 F(u) = 1/2(Feven(u)+Fodd(u)W2Mu) F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu)其中： N = 2MFeven(u)、Fodd(u) 是1/2N個點的傅立葉值 562.3.3 快速傅立葉變換:FFT算法思想FFT算法基本思想通過一個實例來體會一下FFT算法：設(shè)：有函數(shù)f(x)，其 N = 23 = 8 有： f(0), f(1), f(2

24、), f(3), f(4), f(5), f(6), f(7) 計算： F(0), F(1), F(2), F(3), F(4), F(5), F(6),F(7) 572.3.3 快速傅立葉變換:FFT算法思想FFT算法基本思想首先分成奇偶兩組：有： f(0), f(2), f(4), f(6) f(1), f(3), f(5), f(7) 為了利用遞推特性，再分成兩組：有： f(0), f(4) ， f(2), f(6) f(1), f(5) ， f(3), f(7) 582.3.3 快速傅立葉變換:FFT算法思想 f(0), f(4) f(2), f(6) f(1), f(5) f(3),

25、 f(7) F2(0),F2(4) F2(2),F2(6) F2(1),F2(5) F2(3),F2(7) F4(0), F4(4), F4(2), F4(6) F4(1), F4(5), F4(3),F4(7) F8(0), F8(1), F8(2), F8(3), F8(4), F8(5), F8(6), F8(7) 592.3.3 快速傅立葉變換: FFT算法思想分析這些表達式得到如下一些有趣的特性：（1）一個N個點的變換，能夠通過將原始 表達 式分成兩個部分來計算（2）通過計算兩個（N/2）個點的變換。得到 Feven(u)和 Fodd(u)（3）奇部與偶部之和得到F(u)的前(N/2

26、)個值。（4）奇部與偶部之差得到F(u)的后(N/2)個值。 且不需要額外的變換計算。602.3.3 快速傅立葉變換: FFT算法思想歸納快速傅立葉變換的思想：1）通過計算兩個單點的DFT，來計算兩個點的DFT，2）通過計算兩個雙點的DFT，來計算四個點的DFT，以此類推3）對于任何N=2m的DFT的計算，通過計算兩個N/2點的DFT，來計算N個點的DFT612.3.3 快速傅立葉變換:遞推公式推導(dǎo)遞推公式推導(dǎo) FFT算法基于一個叫做遞推加倍的方法。為方便起見我們用下式表達離散傅立葉變換公式 N-1F(u)=1/N f(x) exp(-j2ux/N) x=0 N-1F(u)=1/N f(x)(

27、WN)ux x=0 這里 WN = exp(-j2/N) 是一個常數(shù)622.3.3 快速傅立葉變換:遞推公式推導(dǎo)遞推公式推導(dǎo) 假設(shè)N為： N = 2n 其中n是一個正整數(shù)，因此N可表示為：N = 2M 這里M仍然是一個正整數(shù)。將N = 2M代入上式，得到： 632.3.3 快速傅立葉變換:遞推公式推導(dǎo)遞推公式推導(dǎo) 2M-1 F(u)=1/(2M)f(x)(W2M)ux x=0 M-1 M-1 =1/2 1/Mf(2x)W2Mu(2x)+1/Mf(2x+1)W2Mu(2x+1) x=0 x=0642.3.3 快速傅立葉變換:遞推公式推導(dǎo)遞推公式推導(dǎo)由于： WN = exp(-j2/N) W2M2

28、ux = exp-j22ux/2M = exp-j2ux/M = WMux所以： W2M2xu = WMxu代入上式有：F(u)= M-1 M-1 =1/2 1/M f(2x)W2Mu(2x) + 1/Mf(2x+1)W2Mu(2x+1) x=0 x=0652.3.3 快速傅立葉變換:遞推公式推導(dǎo) M-1 M-1 1/21/Mf(2x)WMux + 1/Mf(2x+1)WMux W2Mu x=0 x=0定義兩個符號： M-1 Feven(u) = 1/Mf(2x)WMux 偶數(shù)部分 x=0u = 0,1,2,M-1 M-1 Fodd (u) = 1/Mf(2x+1)WMux 奇數(shù)部分 x=0

29、u = 0,1,2,M-1662.3.3 快速傅立葉變換:遞推公式推導(dǎo)得出FFT 的第一個遞推公式： F(u)=1/2 ( Feven(u)+Fodd(u)W2Mu )該公式說明F(u)可以通過奇部和偶部之和來計算672.3.3 快速傅立葉變換:遞推公式推導(dǎo)另有：WMu+M = exp-2j(u+M)/M = exp-2ju/M exp-2j = WMuej(-2) = WMu(-1)(-2) = WMu且：W2Mu+M = exp-2j(u+M)/2M = exp-2ju/2M ej(-1) = W2Mu (-1)(-1) = -W2Mu最后有：WMu+M = WMu ； W2Mu+M =

30、-W2Mu682.3.3 快速傅立葉變換:遞推公式推導(dǎo)因為：WMu+M = WMu ； W2Mu+M = -W2Mu得出u+M 的DFT為： M-1F(u+M) = 1/2 1/Mf(2x)WM(u+M)x + x=0 M-1 1/Mf(2x+1)WM(u+M)x W2Mu+M x=0 = 1/2 ( Feven(u)- Fodd(u)W2Mu ) 692.3.3 快速傅立葉變換:遞推公式推導(dǎo)得出FFT的第二個遞推公式： F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu) 該公式說明F(u+M)可以通過F(u)偶部和奇部之差來計算702.3.3 快速傅立葉變換:遞推公式推導(dǎo)得出

31、FFT的兩個遞推公式： F(u) = 1/2(Feven(u)+Fodd(u)W2Mu) F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu) 712.3.3 快速傅立葉變換: 逆向FFT算法逆向FFT算法算法思想描述：用正向變換計算逆向變換 N-1F(u) = 1/N f(x)exp-j2ux/N x=0u = 0, 1, 2, .N-1 N-1 f(x) = F(u)expj2ux/N u=0 x = 0, 1, 2, .N-1722.3.3 快速傅立葉變換:逆向FFT算法逆向FFT算法 在離散逆向變換表達式兩邊同取共軛，并除N N-11/Nf*(x) = 1/N F*(u)

32、 exp-j2ux/N u=0u = 0, 1, 2, .N-1 用正向變換算法計算，得到1/Nf*(x) ，取共軛并乘上N，即得到f(x)732.3.3 快速傅立葉變換:FFT算法實現(xiàn)FFT算法實現(xiàn)幾個關(guān)鍵點1）地址的排序：按位倒序規(guī)則例如：N = 23 = 8原地址 原順序 新地址 新順序 000 f(0) 000 f(0) 001 f(1) 100 f(4) 010 f(2) 010 f(2) 011 f(3) 110 f(6) 100 f(4) 001 f(1) 101 f(5) 101 f(5) 110 f(6) 011 f(3) 111 f(7) 111 f(7)742.3.3 快速傅立