五章節(jié)信源編碼ppt課件

1、第五章第五章 信源編碼信源編碼 信息經(jīng)過信道傳輸?shù)叫潘薜倪^程即為通訊。要做到既不失真又快速地通訊，需求處理兩個問題： 在不失真或允許一定失真條件下，如何提高信息傳輸速度-這是本章要討論的信源編碼問題. 在信道遭到干擾的情況下，如何添加信號的抗干擾才干，同時又使得信息傳輸率最大-這是下章要討論的信道編碼問題. 普通來說，抗干擾能與信息傳輸率二者相互矛盾。然而編碼定理已從實際上證明，至少存在某種最正確的編碼可以處理上述矛盾，做到既可靠又有效地傳輸信息。 信源雖然多種多樣，但無論是哪種類型的信源，信源符號之間總存在相關(guān)性和分布的不均勻性，使得信源存在冗余度。信源編碼的目的就是要減少冗余，提高編碼效率

2、。 信源編碼的根本途徑有兩個: 一是編碼后使序列中的各個符號之間盡能夠地 相互獨立，即解除相關(guān)性-方法包括預(yù)測編 碼和變換編碼. 二是使編碼后各個符號出現(xiàn)的概率盡能夠相等，即均勻化分布-方法主要是統(tǒng)計編碼. 信源編碼常分為無失真信源編碼和限失真信源編碼，前者主要用于文字、數(shù)據(jù)信源的緊縮，后者主要用于圖像、語音信源的緊縮。 本章主要引見信源編碼的根本思緒與主要方法，以無失真、統(tǒng)計編碼為主，期望經(jīng)過本章學(xué)習(xí)能建立起信源緊縮編碼的根本概念。5.1 編碼器及相關(guān)概念 為了分析方便和突出問題的重點，當(dāng)研討信源編碼時，我們把信道編碼和譯碼看成是信道的一部分，從而突出信源編碼。同樣，在研討信道編碼時，可以將

3、信源編碼和譯碼看成是信源和信宿的一部分，從而突出信道編碼。5.1.1 碼的分類 一.編碼器模型 由于信源編碼可以不思索抗干擾問題，所以它的數(shù)學(xué)模型比較簡單。以下圖為一個編碼器模型: 輸入是信源符號集: x為編碼器所用的編碼符號集，包含r個元素 ，稱為碼符號(碼元) . 由碼符號 組成的輸出序列 稱為碼字. 其長度 稱為碼字長度或碼長，全體碼字 的集合C稱為碼或碼書 . 編碼器將信源符號集中的信源符號 或長為N的信源符號序列 變成由碼符號組成的長為的與信源符號一一對應(yīng)的輸出序列。即 :12 ,qSs ss ixrxxx,.,21iWiliWisi12(1,2, )(1,2, )(,), iiii

4、iilijs iqW iqxxxxX 二.碼的分類: 對于編碼器而言，根據(jù)碼符號集合X中碼元的個數(shù)不同以及碼字長度能否一致，有以下一些常用的編碼方式： (1)二元碼和r元碼 假設(shè)碼符號集 ，編碼所得碼字為一些適宜在二元信道中傳輸?shù)亩蛄?，那么稱二元碼。二元碼是數(shù)字通訊與計算機系統(tǒng)中最常用的一種碼。假設(shè)碼符號集共有 r 個元素，那么所得之碼稱為 r 元碼. (2)等長碼 假設(shè)一組碼中一切碼字的長度都一樣-即 ，那么稱為等長碼.0,1X ,1,ill iq (3) 變長碼 假設(shè)一組碼中碼字的碼長各不一樣即碼字長度 不等，那么稱為變長碼 . 如表中“編碼1為等長碼，“編碼2為變長碼。il信源符號s

5、i符號出現(xiàn)概率p(si)編碼1編碼2s1p(s1)000s2p (s2)0101s3p (s3)10001s4p (s4)11101 (4)分組碼 假設(shè)每個信源符號按照固定的碼表映射成一個碼字，那么稱為分組碼。否那么就是非分組碼. 假設(shè)采用分組編碼方法，需求分組碼具有某些屬性，以保證在接納端可以迅速而準(zhǔn)確地將接納到的碼譯成與信源符號對應(yīng)的音訊。下面討論分組碼的一些直觀屬性。 1非奇特碼和奇特碼 假設(shè)一組碼中一切碼字都不一樣(即一切信源符號映射到不同的碼符號序列)，那么稱為非奇特碼。反之，那么為奇特碼。如表中的“編碼2是奇特碼，其他碼是非奇特碼。()ip a1a2a3a4a概率信源符號 編碼1編

6、碼2編碼3編碼4編碼51/20000011/4010110011/8101001100011/81110111110001 2同價碼 假設(shè)碼符號集X： 中每個碼符號所占的傳輸時間都一樣，那么所得的碼為同價碼。 我們普通討論同價碼，對同價碼來說等長碼中每個碼字的傳輸時間一樣，而變長碼中每個碼字的傳輸時間就不一定一樣。rxxx,.,21 3碼的N次擴展碼 假定某一碼，它把信源 中的符號 一一變換成碼C中的碼字 ，那么碼C的N次擴展碼是一切N個碼字組成的碼字序列的集合。12 ,qSs ss isiW 例如：假設(shè)碼 滿足： 那么碼C的N次擴展碼集合 ,其中： 即碼C的N次擴展碼中，每個碼字 與信源的N

7、次擴展信源 中的每個信源符號 是一一對應(yīng)的：12,qCW WW 12(,), ,iiiiiiliilsWxxxsS xX 12,NqBB BB 121,; ,1, ; 1,NNiiiiNBW WWiiqiq iBNS12,iiiiNsss 12(,), ,NlNiiiiiiiBW WWSWC 4獨一可譯碼 假設(shè)恣意一串有限長的碼符號序列只能被獨一地譯成所對應(yīng)的信源符號序列，那么此碼稱為獨一可譯碼或稱單義可譯碼。否那么就稱為非獨一可譯碼或非單義可譯碼。 假設(shè)要使某一碼為獨一可譯碼，那么對于恣意給定的有限長的碼符號序列，只能被獨一地分割成一個個的碼字。 例如：對于二元碼 ，當(dāng)恣意給定一串碼字序列，

8、例如“10001101，只可獨一地劃分為1,00,01,1,01，因此是獨一可譯碼；而對另一個二元碼 ，當(dāng)碼字序列為“01001時，可劃分為0,10,01或01,0,01，所以是非獨一可譯的。11,01,00C 20,10,01C 對獨一可譯碼又分為即時碼和非即時碼：假設(shè)在接納端收到一個完好的碼字后，就能立刻進展譯碼，這樣的碼叫做即時碼；而在接納端收到一個完好的碼字后，還需等下一個碼字接納后才干判別能否可以譯碼，這樣的碼叫做非即時碼。 即時碼又稱為非延伸碼，對即時碼而言，在碼本中恣意一個碼字都不是其它碼字的前綴部分。對非即時碼來說，有的碼是獨一可譯的，有的碼是非獨一可譯的，主要取決于碼的總體構(gòu)

9、造。 綜上所述，可將碼作所示的分類：5.1.2 碼樹 對于給定碼字的全體集合，可以用碼樹來描畫。 對于r進制的碼樹，如下頁圖所示，其中圖(a)為二元碼樹，圖(b)為三元碼樹。在碼樹中點是樹根，從樹根伸出個樹枝，構(gòu)成元碼樹。樹枝的盡頭是節(jié)點，普通中間節(jié)點會伸出樹枝，不伸出樹枝的節(jié)點為終端節(jié)點，編碼時應(yīng)盡量在終端節(jié)點安排碼字。 碼樹中自樹根經(jīng)過一個分枝到達一階節(jié)點，一階節(jié)點最多為r個，二階節(jié)點的能夠個數(shù)為r2個，n階節(jié)點最多有rn個，假設(shè)將從每個節(jié)點發(fā)出的個分枝分別標(biāo)以0，1，r-1，那么每個n階節(jié)點需求用n個r元數(shù)字表示。假設(shè)指定某個n階節(jié)點為終端節(jié)點，用于表示一個信源符號，那么該節(jié)點就不再延伸

10、，相應(yīng)的碼字即為從樹根到此端點的分枝標(biāo)號序列，該序列長度為n，用這種方法構(gòu)造的碼滿足即時碼的條件，由于從樹根到每一個終端節(jié)點所走的途徑均不一樣，所以一定滿足對即時碼前綴的限制。假設(shè)有個q信源符號，那么在碼樹上就要選擇q個終端節(jié)點，用相應(yīng)r的元根本符號表示這些碼字。 假設(shè)樹碼的各個分支都延伸到最后一級端點，此時將共有個碼字，這樣的碼樹稱為整樹，如圖(a)所示。否那么就稱為非整樹，如圖(b)所示，這時的碼字就不是等長碼了。 因此，碼樹與碼之間具有如下一一對應(yīng)的關(guān)系： 樹根碼字起點； 樹枝數(shù)碼的進制數(shù)； 節(jié)點碼字或碼字的一部分； 終端節(jié)點碼字； 階數(shù)碼長； 非整樹變長碼； 整樹等長碼。5.1.3 K

11、raft不等式 利用碼樹可以判別給定的碼能否為獨一可譯碼，但需求畫出碼樹。在實踐中，我們可以利用克拉夫特Kraft不等式，直接根據(jù)各碼字的長度來判別獨一可譯碼能否存在，即各碼字的長度應(yīng)符合克拉夫特不等式： 式中，r為進制數(shù)也即碼符號的個數(shù)，q為信源符號數(shù)。11iqlir Kraft不等式是獨一可譯碼存在的充要條件，其必要性表如今假設(shè)碼是獨一可譯碼，那么必定滿足Kraft不等式;充分性表如今假設(shè)滿足Kraft不等式，那么這種碼長的獨一可譯碼一定存在，但并不表示一切滿足Kraft不等式的碼一定是獨一可譯碼。 因此，克拉夫特不等式是獨一可譯碼存在的充要條件，而不是獨一可譯碼的充要條件。5.2 變長編

12、碼 變長碼往往在碼長的平均值不很大時，就可編出效率很高而且無失真的碼，其平均碼長受香農(nóng)第一定理所限定，即： 假設(shè)對信源離散無記憶信源S的N次擴展信源 進展編碼，那么總可以找到一種編碼方法，構(gòu)成獨一可譯碼，使信源S中每個信源符號所需的平均碼長滿足：NSrSHNLNrSHNlog)(1log)( 且當(dāng) 時有： 其中， 為N次擴展信源的平均碼長， 為信源符號擴展序列 的碼長. 為對擴展信源進展編碼后，每個信源符號 編碼所需的等效的平均碼長。 N1lim() ()() lo g() qNrririNiLHSHSp ap aN1()NqNiiiLpl iliNLN 要做到無失真的信源編碼，平均每個信源符

13、號所需最少的r元碼元數(shù)為信源的熵 。 即 它是無失真信源緊縮的極限值。 假設(shè)編碼的平均碼長小于信源的熵值 ，那么獨一可譯碼不存在，在譯碼或反變換時必然要帶來失真或過失。 經(jīng)過對擴展信源進展變長編碼，當(dāng)N時，平均碼長( )rHS( )rHS( )rHS 無失真信源編碼的本質(zhì)： 對離散信源進展適當(dāng)?shù)淖儞Q，使變換后構(gòu)成的新的碼符號信源(即信道的輸入信源)盡能夠為等概率分布，以使新信源的每個碼符號平均所含的信息量到達最大，使信道的信息傳輸率到達信道容量，實現(xiàn)信源與信道理想的統(tǒng)計匹配。這實踐上就是香農(nóng)第一定理的物理意義。 為了衡量各種編碼能否到達極限情況，定義變長碼的編碼效率為： 常經(jīng)過編碼效率來衡量各

14、種編碼的優(yōu)劣. 為了衡量各種編碼與最正確碼的差距，定義碼的剩余度為： 信息傳輸率定義為： 留意:雖然與在數(shù)值上一樣，但它們的單位不同，編碼效率沒有單位，而信息傳輸率的單位是比特/碼符號。LSHr)(LSHr)(11LSHR)( 在二元無噪無損信道中 在二元信道中，假設(shè)編碼效率 =1，R=1比特碼符號，那么到達信道的信道容量，此時編碼效率最高，碼的剩余度為零。 前面曾經(jīng)闡明，對于某一個信源和某一符號集來說，凡是滿足克拉夫特不等式的獨一可譯碼可以有多種，在這些獨一可譯碼中，假設(shè)有一種或幾種碼，其平均編碼長度小于一切其他獨一可譯碼的平均編碼長度，那么該碼稱為最正確碼或緊致碼。()2, ()(), r

15、HSrHSHSL 為了使得平均編碼長度為最小，必需將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字。能獲得最正確碼或次最正確碼的編碼方法有很多，本節(jié)重點引見：香農(nóng)(shannon) 編碼、費諾(Fano) 編碼、霍夫曼(Huffman)編碼。5.2.1 香農(nóng)碼 香農(nóng)第一定理指出，可選擇每個碼字的長度滿足關(guān)系式： 或： x 表示不小于 x 的整數(shù)。按不等式選擇的碼長所構(gòu)成的碼稱香農(nóng)碼。香農(nóng)碼滿足克拉夫特不等式，所以一定存在對應(yīng)碼字的長度的獨一可譯碼。log()log()1(1, )iiip slp siq 1lo g(1,)()iiliqps 普通情況下，按照香農(nóng)編碼方法編出來的碼，其平

16、均碼長不是最短的，也即不是緊致碼(最正確碼)。只需當(dāng)信源符號的概率分布使不等式左邊的等號成立時，編碼效率才到達最高。 香農(nóng)碼的編碼步驟如下： 1將個信源符號按概率遞減的方式進展陳列： 2按香農(nóng)不等式計算出每個信源符號的碼長 ； 3為了編成獨一可譯碼，計算第i個信源符號的累加概率 4將累加概率 用二進制數(shù)表示。 5取 對應(yīng)二進制數(shù)的小數(shù)點后位構(gòu)成該信源符號的二進制碼字。12qppp il11iikkPp iPiP 例例:設(shè)信源共有七個信源符號，其概率分布如設(shè)信源共有七個信源符號，其概率分布如表所示，試對該信源進展香農(nóng)編碼。表所示，試對該信源進展香農(nóng)編碼。 解解:計算過程見下頁計算過程見下頁 碼的

17、性能分析：碼的性能分析： 經(jīng)過計算可得此信源的熵經(jīng)過計算可得此信源的熵: (比特符號比特符號) 而碼的平均長度而碼的平均長度: (二元碼符號符號二元碼符號符號) 編碼效率：編碼效率：71( )()log()2.61iiiH Sp ap a 71()3 .1 4iiiLp al 0.831 ()ip aiP1log( )ip sil1a2a3a4a5a6a7a概率累加概率碼長信源符號對應(yīng)的二進制數(shù)碼字0.2000.0002.3430000.190.20.00112.4130010.180.390.01102.4830110.170.570.10012.5631000.150.740.10112.

18、7431010.100.890.11103.34411100.010.990.11111106.66711111105.2.2 費諾碼 費諾編碼屬于概率匹配編碼，但它普通也不是最正確的編碼方法，只需當(dāng)信源的概率分布呈現(xiàn) 分布方式的條件下，才干到達最正確碼的性能。( )ilip sr 費諾碼的編碼步驟如下： 1信源符號以概率遞減的次序陳列起來； 2將陳列好的信源符號按概率值劃分成兩大組，使每組的概率之和接近于相等，并對每組各賦予一個二元碼符號“0和“1； 3將每一大組的信源符號再分成兩組，使劃分后的兩個組的概率之和接近于相等，再分別賦予一個二元碼符號； 4依次下去，直至每個小組只剩一個信源符號為

19、止； 5信源符號所對應(yīng)的碼字即為費諾碼。 例例:將以下音訊按二元費諾碼方法進展編碼。將以下音訊按二元費諾碼方法進展編碼。 解解:其編碼過程如下頁：其編碼過程如下頁： 碼的性能分析：碼的性能分析： 此信源的熵此信源的熵 (比特符號比特符號)， 而碼的平均長度而碼的平均長度 (二元碼符號符號二元碼符號符號) 顯然，該碼是緊致碼，編碼效率：顯然，該碼是緊致碼，編碼效率： 該碼之所以能到達最正確，是由于信源符號的該碼之所以能到達最正確，是由于信源符號的概率分布正好滿足式，否那么，在普通情況下概率分布正好滿足式，否那么，在普通情況下是無法到達編碼效率等于是無法到達編碼效率等于“1的。的。 ( )2.75

20、H S 2.75L 1 費諾碼具有如下的性質(zhì)： 費諾碼的編碼方法實踐上是一種構(gòu)造碼樹的方法，所以費諾碼是即時碼。 費諾碼思索了信源的統(tǒng)計特性，使概率大的信源符號能對應(yīng)碼長較短的碼字，從而有效地提高了編碼效率。 費諾碼不一定是最正確碼。由于費諾碼編碼方法不一定能使短碼得到充分利用:當(dāng)信源符號較多時，假設(shè)有一些符號概率分布很接近時，分兩大組的組合方法就會很多。能夠某種分大組的結(jié)果，會使后面小組的“概率和相差較遠，從而使平均碼長添加。 r 元費諾碼 前面討論的費諾碼是二元費諾碼，對r元費諾碼，與二元費諾碼編碼方法一樣，只是每次分組時應(yīng)將符號分成概率分布接近的r個組。5.2.3 霍夫曼碼 1952年，

21、霍夫曼Huffman提出了一種構(gòu)造最正確碼的方法，這是一種最正確的逐個符號的編碼方法，普通就稱作霍夫曼碼。 設(shè)信源 ，其對應(yīng)的概率分布為 ，那么對二元霍夫曼碼而言，其編碼步驟如下： 12 ,.,qSs ss 12(),.,iqp sppp 1將q個信源符號按概率遞減的方式陳列起來； 2用“0、“1碼符號分別表示概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個新的符號，從而得到只包含q-1個符號的新信源，稱之為S信源的S1縮減信源； 3將縮減信源中的符號仍按概率大小以遞減次序陳列，再將其最后兩個概率最小的符號合并成一個符號，并分別用“0、“1碼符號表示，這樣又構(gòu)成了由q-2個符號構(gòu)

22、成的縮減信源S2； 4依次繼續(xù)下去，直到縮減信源只剩下兩個符號為止，將這最后兩個符號分別用“0、“1碼符號表示； 5從最后一級縮減信源開場，向前前往，沿信源縮減方向的反方向取出所編的碼元，得出各信源符號所對應(yīng)的碼符號序列，即為對應(yīng)信源符號的碼字。 例例:對離散無記憶信源對離散無記憶信源 進展霍夫曼編碼。進展霍夫曼編碼。 解解:編碼過程如表所示：編碼過程如表所示： 1)將信源符號按概率大小由大至小排序。將信源符號按概率大小由大至小排序。 2)從概率最小的兩個信源符號和開場編碼，并按一從概率最小的兩個信源符號和開場編碼，并按一定的規(guī)那么賦予碼符號，如下面的信源符號小概率為定的規(guī)那么賦予碼符號，如下

23、面的信源符號小概率為“1，上面的信源符號大約率為，上面的信源符號大約率為“0。假設(shè)兩支路概。假設(shè)兩支路概率相等，仍為下面的信源符號為率相等，仍為下面的信源符號為“1 上面的信源符號為上面的信源符號為“0。 3)將已編碼兩個信源符號概率合并，重新排隊，編將已編碼兩個信源符號概率合并，重新排隊，編碼。碼。 4)反復(fù)步驟反復(fù)步驟3直至合并概率等于直至合并概率等于“1.0為止。為止。 5)從概率等于從概率等于“1.0端沿合并道路逆行至對應(yīng)音訊端沿合并道路逆行至對應(yīng)音訊編碼編碼.12345()0.40.20.20.10.1iSsssssp s 碼的性能分析： 信源的熵為： (比特符號) 從 ，可得平均碼

24、長為： 編碼效率為：( )2.61H S :2,2,3,3,3,4,4il71()2 .7 2iiiLpal96.0)(LSH 按霍夫曼碼的編碼方法，可知這種碼有如下特征： 它是一種分組碼：各個信源符號都被映射成一組固定次序的碼符號； 它是一種獨一可解的碼：任何碼符號序列只能以一種方式譯碼； 它是一種即時碼：由于代表信源符號的節(jié)點都是終端節(jié)點，因此其編碼不能夠是其它終端節(jié)點對應(yīng)的編碼的前綴，霍夫曼編碼所得的碼字一定是即時碼。所以一串碼符號中的每個碼字都可不思索其后的符號直接解碼出來。 霍夫曼碼的譯碼：對接納到的霍夫曼碼序列可經(jīng)過從左到右檢查各個符號進展譯碼。 闡明： 霍夫曼碼是一種即時碼，可用

25、碼樹方式來表示。 每次對縮減信源最后兩個概率最小的符號，用“0和“1碼是可以恣意的，所以可得到不同的碼，但碼長不變，平均碼長也不變。 當(dāng)縮減信源中縮減合并后得到的新符號的概率與其他信源符號概率一樣時，從編碼方法上來說，它們概率的排序是沒有限制的，因此也可得到不同的碼。 即對給定信源，用霍夫曼編碼方法得到的碼并非是獨一，但平均碼長不變。 r 元霍夫曼碼 對二元霍夫曼碼的編碼方法同樣可以推行到元編碼中。不同的只是每次把概率最小的個符號合并成一個新的信源符號，并分別用0，1，r-1，等碼元表示。 為了使短碼得到充分利用，使平均碼長為最短，必需使最后一步的縮減信源有r個信源符號。 因此對于r元編碼，信

26、源S的符號個數(shù)q必需滿足：q=n(r-1)+r. 其中，n表示縮減的次數(shù)，r-1為每次縮減所減少的信源符號個數(shù)。 對于二元碼r=2，信源符號個數(shù)必需滿足：q=n+r,因此q可等于恣意整正數(shù)。 留意: 對于r元碼時，不一定能找到一個使式q=n(r-1)+r成立。在不滿足上式時，可假設(shè)一些信源符號： 作為虛擬的信源，并令它們對應(yīng)的概率為零，即： ,而使 能成立，這樣處置后得到的r元霍夫曼碼可充分利用短碼，一定是緊致碼。tqqqsss,.,210.21tqqqppp(1)qtn rr 例例 對信源進展四元霍夫曼碼編碼。表列出對信源進展四元霍夫曼碼編碼。表列出了四元霍夫曼碼的編碼方法及其對應(yīng)的碼了四元

27、霍夫曼碼的編碼方法及其對應(yīng)的碼字。字。5.3 限失真信源編碼 由實踐生活閱歷我們知道，普通人們并不要求完全無失真地恢復(fù)音訊。對人的心思視覺研討闡明，人們在察看圖像時主要是尋覓某些比較明顯的目的特征，而不是定量地分析圖像中每個像素的亮度，或者至少不是對每個像素都等同地分析。例如觀看一段視頻或察看一幅圖像，人們能夠會關(guān)注其主要情節(jié)，對視頻或圖像中的細節(jié)并不是那么留意，此時便允許視頻或圖像有一定程度的失真。 由香農(nóng)第一定理知，無論哪種信道，只需信息傳輸率R小于信道容量C，總能找到一種編碼方法，使得在信道上能以恣意小的錯誤概率，以恣意接近的傳輸率來傳送信息。 實踐信道中，信源輸出的信息傳輸率R普通都會

28、超越信道容量，因此也就不能夠?qū)崿F(xiàn)完全無失真地傳輸信源的信息。 由香農(nóng)第三定理知，在允許一定失真度D的情況下，信源輸出的信息傳輸率可緊縮到R(D)值，只需信息傳輸率R大于R(D)，一定能找到一種編碼方法，使得譯碼后的失真小于D。香農(nóng)第三定理從實際上給出了信息傳輸率與允許失真之間的關(guān)系，奠定了信息率失真實際的根底。信息率失真實際是進展量化、數(shù)模轉(zhuǎn)換、頻帶緊縮和數(shù)據(jù)緊縮的實際根底。 普通情況下信源編碼可分為離散信源編碼、延續(xù)信源編碼和相關(guān)信源編碼三類。前兩類編碼方法主要討論獨立信源編碼問題，后一類編碼方法討論非獨立信源編碼問題。離散信源可做到無失真編碼，而延續(xù)信源那么只能做到限失真編碼。5.4 適用

29、信源編碼方法 無失真和限失真信源編碼定理，闡明了最正確碼的存在性，但沒有給出詳細構(gòu)造碼的方法，適用的編碼方法需求根據(jù)信源的詳細特點來決議。 霍夫曼碼在實踐中已得到運用，但它仍存在一些分組碼所具有的缺陷，例如概率特性必需準(zhǔn)確地測定，假設(shè)信源概率特性稍有變化，就必需改換碼表；對于二元信源，常需多個符號合起來編碼，才干獲得較好的效果，但是假設(shè)合并的符號數(shù)目不大時，編碼效率提高得不多，特別是對于相關(guān)信源，霍夫曼編碼不能給出令人稱心的結(jié)果。因此在適用中常需作一些改良，同時也就有必要研討非分組碼。 在編碼實際的指點下，先后出現(xiàn)了許多性能優(yōu)良的編碼方法，本節(jié)引見一些適用的編碼方法 .5.4.1 游程編碼 游

30、程Run-Length，簡記RL是指符號序列中各個符號延續(xù)反復(fù)出現(xiàn)而構(gòu)成符號串的長度，又稱游程長度或游長。 游程編碼Run-Length Coding，簡記RLC就是將這種符號序列映射成游程長度和對應(yīng)符號序列的位置的標(biāo)志序列。假設(shè)知道了游程長度和對應(yīng)符號序列的位置的標(biāo)志序列，就可以完全恢復(fù)出原來的符號序列。 游程編碼特別適用于對相關(guān)信源的編碼。對二元相關(guān)信源，其輸出序列往往會出現(xiàn)多個延續(xù)的“0或延續(xù)的“1。在信源輸出的二元序列中，延續(xù)出現(xiàn)的“0符號稱為“0游程，延續(xù)出現(xiàn)的“1符號稱為“1游程，對應(yīng)延續(xù)同一符號的個數(shù)分別稱為“0游程長度和“1游程長度，由于游程長度是隨機的，其取值可以是1，2，3

31、，。 對二元序列，“0游程和“1游程總是交替出現(xiàn)的，假設(shè)規(guī)定二元序列是以“0開場的，那么第一個游程是“0游程，第二個游程必為“1游程，第三個游程又是“0游程等等。將任何二元序列變換成游程長度序列，這種變換是一一對應(yīng)的，因此是可逆的、無失真的。 由于游程長度是隨機的、多值的，所以游程序列本身是多元序列，對游程序列可以按霍夫曼編碼或其他編碼方法進展處置以到達緊縮碼率的目的。 對于r元序列也存在相應(yīng)的游程序列。在r元序列中，可有r種游程。延續(xù)出現(xiàn)的符號 的游程，其長度L(i)就是“i游程長度。用L(i)也可構(gòu)成游程序列，但此時由于游程所對應(yīng)的信源符號可有r種，因此，這種變換必需再加一些標(biāo)志信源符號取

32、值的識別符號，才干使編碼以后的游程序列與原來的r元序列一一對應(yīng)。所以把r元序列變換成游程序列再進展緊縮編碼通常效率不高。ia 游程編碼仍是變長碼，有著變長碼固有的缺陷，即需求大量的緩沖和優(yōu)質(zhì)的通訊信道。此外，由于游程長度可從“1直到無窮大，這在碼字的選擇和碼表的建立方面都有困難，實踐運用時髦需采取某些措施來改良。例如，通常長游程出現(xiàn)的概率較小，所以對于這類長游程所對應(yīng)的小概率碼字，在實踐運用時采用截斷處置的方法。 游程編碼已在圖文、圖像傳輸?shù)韧ㄓ嵐こ碳夹g(shù)中得到運用。在實踐中還經(jīng)常將游程編碼與其他編碼方法綜合起來運用，以期得到更好的緊縮效果。 下面以三類機中運用的緊縮編碼的國際規(guī)范MH編碼為例闡

33、明游程編碼的實踐運用。 MH編碼: 文件是指普通文件、圖紙、手寫稿、表格、報紙等文件的，這種信源是黑白二值的，也即信源為二元信源q=2。 MH編碼是一維編碼方案，它是一行一行的對文件數(shù)據(jù)進展編碼。編碼將游程編碼和霍夫曼碼相結(jié)合，是一種改良的霍夫曼碼。 對黑白二值文件，每一行由延續(xù)出現(xiàn)的“白用碼符號0表示像素或延續(xù)出現(xiàn)“黑用碼符號1表示像素組成。MH碼分別對“黑、“白像素的不同游程長度進展霍夫曼編碼，構(gòu)成黑、白兩張霍夫曼碼表。MH碼的編、譯碼都經(jīng)過查表進展。 MH碼以國際電報咨詢委員會CCITT確定的8幅規(guī)范文件樣張為樣本信源，對這8幅樣張作統(tǒng)計，計算出“黑、“白各種游程長度的出現(xiàn)概率，然后根據(jù)

34、這些概率分布，分別得出“黑、“白游程長度的霍夫曼碼表。 碼編碼規(guī)那么如下： 1)游程長度在063時，碼字直接用相應(yīng)的終端碼表示。 2)游程長度在641728，用一個構(gòu)成碼加上一個終端碼作為相應(yīng)碼字。 3)規(guī)定每行都從白游程開場。假設(shè)實踐出現(xiàn)黑游程開場的話，那么在行首加上長度為零的白游程碼字，每行終了時用一個終了碼(EOL)作標(biāo)志。 4)每頁文件開場第一個數(shù)據(jù)前加一個終了碼，每頁結(jié)尾延續(xù)運用6個終了碼表示結(jié)尾。 5)譯碼時，每一行的碼都應(yīng)恢復(fù)出1728個像素，否那么有錯。 6)為了在傳輸時可實現(xiàn)同步操作，規(guī)定T為每個編碼行的最小傳輸時間，普通規(guī)定T最小為20，最大為5。假設(shè)編碼行傳輸時間小于T，

35、那么在終了碼之前填上足夠的“0碼元(稱填充碼)。 假設(shè)采用編碼僅僅是用于存儲，那么可省去步驟中的4)至6)步。 例例 設(shè)某頁文件中某一掃描行的像素點為：設(shè)某頁文件中某一掃描行的像素點為： 17白白 5黑黑 55白白 10黑黑 l641白白 解解:經(jīng)過查表可得該掃描行的碼為：經(jīng)過查表可得該掃描行的碼為： 17白白 5黑黑 55白白 10黑黑 1600白白+ 41白白 EOL 101011 0011 01011000 0000100 010011010 00101010 000000000001 該行經(jīng)編碼后只需用該行經(jīng)編碼后只需用54位二元碼元，而原來位二元碼元，而原來一行共有一行共有1728個

36、像素，如用個像素，如用“0表示白，用表示白，用“l(fā)表示黑，那么共需表示黑，那么共需1728位二元碼元?？梢?，這一位二元碼元?？梢?，這一行數(shù)據(jù)的緊縮比為行數(shù)據(jù)的緊縮比為1728:5432，因此緊縮效率，因此緊縮效率很高。很高。5.4.2 算術(shù)編碼 前面所討論的無失真編碼，都是建立在信源符號與碼字一一對應(yīng)的根底上的，這種編碼方法我們通常稱為塊碼或分組碼，此時信源符號普通應(yīng)是多元的，而且不思索信源符號之間的相關(guān)性。假設(shè)要對最常見的二元序列進展編碼，那么需采用游程編碼或合并信源符號等方法，把二元序列轉(zhuǎn)換成多值符號，轉(zhuǎn)換后這些多值符號之間的相關(guān)性也是不予思索的。這就使信源編碼的匹配原那么不能充分滿足，編

37、碼效率普通就不高。 為了抑制這種局限性，就需求跳出分組碼的范疇，研討非分組碼的編碼方法，而下面要引見的算術(shù)編碼即為一種非分組碼。在算術(shù)編碼中，信源符號和碼字間的一一對應(yīng)關(guān)系并不存在，它是一種從整個符號序列出發(fā)，采用遞推方式進展編碼的方法 算術(shù)編碼的根本思緒是：從整個符號序列出發(fā)，將各信源序列的概率映射到0，1區(qū)間上，使每個符號序列對應(yīng)于區(qū)間內(nèi)的一點，也就是一個二進制的小數(shù)。這些點把0，1區(qū)間分成許多小段，每段的長度等于某一信源序列的概率。再在段內(nèi)取一個二進制小數(shù)，其長度可與該序列的概率匹配，到達高效率編碼的目的。這種方法與香農(nóng)編碼法有些類似，只是它們思索的信源對象有所不同，在香農(nóng)編碼中思索的是

38、單個信源符號，而在算術(shù)碼中思索的是信源符號序列。 假設(shè)信源符號集為 ，信源序列 ，那么總共有 種能夠的序列。由于思索的是整個符號序列，因此整頁紙上的信息也許就是一個序列，所以序列長度L普通都很大。在實踐中很難得到對應(yīng)信源序列的概率，普通我們從知的信源符號概率 遞推得到。12,nAaaa 12(,),iiiliLilaaaaaA Ln12,nPppp 定義各符號的積累概率為： 那么可得 由于 和 都是小于“1的正數(shù)，可用0，1區(qū)間內(nèi)的兩個點來表示，而 就是這兩個點之間的長度，如下圖。 11iillPp 12131222110,nnnPPp PppPpPPp iP1iP 1ip 不同的信源符號有不

39、同的概率區(qū)間，它們互不重疊，因此可以用這個小區(qū)間中的恣意一點的取值，作為該信源符號的代碼。我們所需確定的是這個代碼所對應(yīng)的長度，應(yīng)使這個長度與信源符號的概率相匹配。 同樣對于整個信源符號序列而言，要把一個算術(shù)碼字賦給它，那么必需確定這個算術(shù)碼字所對應(yīng)的位于0，1區(qū)間內(nèi)的實數(shù)區(qū)間，即由整個信源符號序列的概率本身確定0和1之間的一個實數(shù)區(qū)間。隨著符號序列中的符號數(shù)量的添加，用來代表它的區(qū)間減小，而用來表達區(qū)間所需的信息單位(如比特)的數(shù)量那么增大。 每個符號序列中隨著符號數(shù)量的添加，即信源符號的不斷輸入，用于代表符號序列概率的區(qū)間將隨之減小，區(qū)間減小的過程如下圖。 區(qū)間寬度的遞推公式為： 累積概率

40、的遞推公式為： 其中 為信源符號序列的累積概率， 為信源符號序列的結(jié)合概率，而 ， 。 我們可取該小區(qū)間內(nèi)的一點來代表這個信源符號序列，那么選取此點方法可以有多種，實踐中常取小區(qū)間的下界值。對信源符號序列的編碼方法也可有多種，下面引見常用的一種算術(shù)編碼方法。()( ) ( )( ) ( )()0,1ArAp rpp rprr ()( )( )( )0,1PrPpP rr ( )P ( )p (0)0P (1)(0)Pp 將信源符號序列 的累積概率值寫成二進位的小數(shù) ，取小數(shù)點后L位，假設(shè)后面有尾數(shù)，就進位到第L位，并使L滿足: 式中 表示大于或等于x的最小整數(shù)。 這樣得到信源符號序列所對應(yīng)的一

41、個算術(shù)碼： 12()0., 0,1LiPc ccc 1l o g()Lp x 12Lc cc 假設(shè)是多元信源序列，那么其累積概率和區(qū)間寬度的遞推公式分別為： 其中 為信源符號序列的累積概率， 為信源符號序列的結(jié)合概率，而 按式 計算。()()()()()()()()kkkkkPaPpP aAapaAp a ( )P ( )p ()kkP aP 11iillPp 例例 設(shè)二元無記憶信源設(shè)二元無記憶信源 ，其中，其中 。對二元序列對二元序列 進展算術(shù)編碼。進展算術(shù)編碼。 解：根據(jù)上面引見的編碼方法，先計算信源解：根據(jù)上面引見的編碼方法，先計算信源符號序列符號序列 的結(jié)合概率：的結(jié)合概率： 決議信源

42、符號序列的算術(shù)碼字長度：決議信源符號序列的算術(shù)碼字長度：0,1S 13(0),(1)44pp 11111100 62( )(11111100)(1)(0)pppp 62(3/4) (1/4)0.01112366 1lo g6 .4 97()Lp 再計算信源符號序列的累積概率，按遞推公式有： 信源符號序列 的累積概率值的變化及區(qū)間寬度減小的過程如下圖。累積概率值 即為輸入符號序列“11111100區(qū)間的下界值。( )(11111100)PP (0)(10)(110)(1110)(11110)(111110)pppppp 2345(1/4) (3/4)(1/4) (3/4)(1/4) (3/4)(

43、1/4) (3/4)(1/4) (3/4)(1/4) 0.82202148 20.1101001001 ()P 取 二進制表示小數(shù)點后L位，得到信源符號序列的算術(shù)碼字為： 。 本例對輸入信源符號序列進展算術(shù)編碼后平均碼長為： 編碼效率為： 由于這里需編碼的序列長為八位，所以一共要把半開區(qū)間0，1分成256個小區(qū)間，以對應(yīng)任一個能夠的序列。由于任一個碼字必在某個特定的區(qū)間，所以其解碼具有獨一性。 ( )P 110101078L ( )0.8110.9277/8H SL 算術(shù)碼的譯碼: 對二元算術(shù)碼而言，其譯碼過程是一系列比較過程： 每一步比較 與 ， 這里 為前面已譯出的序列串， 是序列串 對應(yīng)

44、的寬度， 是序列 的累積概率值，即為 對應(yīng)區(qū)間的下界限， 是此區(qū)間內(nèi)下一個輸入為符號“0所占的子區(qū)間寬度。 譯碼規(guī)那么為： 假設(shè) ，那么譯輸出符號為“0； 假設(shè) ，那么譯輸出符號為“1。( )CP ( ) (0)Ap( )A ( )P ( ) (0)Ap( )CP ( ) (0)Ap( )CP ( ) (0)Ap( )CP 從性能上來看，算術(shù)編碼具有許多優(yōu)點，它所需的參數(shù)較少、編碼效率高、編譯碼簡單，不象霍夫曼碼那樣需求一個很大的碼表，在實踐實現(xiàn)時，常用自順應(yīng)算術(shù)編碼對輸入的信源序列自順應(yīng)地估計其概率分布。算術(shù)編碼在圖像數(shù)據(jù)緊縮規(guī)范如JPEG中得到廣泛的運用。5.4.3 預(yù)測編碼 預(yù)測編碼是數(shù)

45、據(jù)緊縮三大經(jīng)典技術(shù)統(tǒng)計編碼、預(yù)測編碼、變換編碼之一，它是建立在信源數(shù)據(jù)相關(guān)性之上的。由信息實際可知，對于相關(guān)性很強的信源，條件熵可遠小于無條件熵，因此人們常采用盡量解除相關(guān)性的方法，使信源輸出轉(zhuǎn)化為獨立序列，以利于進一步緊縮碼率。 常用的解除相關(guān)性的措施是預(yù)測和變換，其本質(zhì)都是進展序列的一種映射。普通來說，預(yù)測編碼有能夠完全解除序列的相關(guān)性，但必需確知序列的概率特性；變換編碼普通只解除矢量內(nèi)部的相關(guān)性，但它可有許多可供選擇的變換方法，以順應(yīng)不同的信源特性。下面引見預(yù)測編碼的普通實際與方法。 預(yù)測編碼的根本思想是經(jīng)過提取與每個信源符號有關(guān)的新信息，并對這些新信息進展編碼來消除信源符號之間的相關(guān)性

46、。實踐中常用的新信息為信源符號的當(dāng)前值與預(yù)測值的差值，這里正是由于信源符號間存在相關(guān)性，所以才使預(yù)測成為能夠，對于獨立信源，預(yù)測就沒有能夠。 預(yù)測的實際根底主要是估計實際。所謂估計就是用實驗數(shù)據(jù)組成一個統(tǒng)計量作為某一物理量的估值或預(yù)測值。假設(shè)估值的數(shù)學(xué)期望等于原來的物理量，就稱這種估計為無偏估計；假設(shè)估值與原物理量之間的均方誤差最小，就稱之為最正確估計，基于這種方法進展預(yù)測，就稱為最小均方誤差預(yù)測，所以也就以為這種預(yù)測是最正確的。 要實現(xiàn)最正確預(yù)測就是要找到計算預(yù)測值的預(yù)測函數(shù)。 設(shè)有信源序列 ，k階預(yù)測就是由 的前k個數(shù)據(jù)來預(yù)測 。 可令預(yù)測值為： 式中 是待定的預(yù)測函數(shù)。要使預(yù)測值具有最小

47、均方誤差，必需確知k個變量的結(jié)合概率密度函數(shù) ，這在普通情況下較難得到，因此常用比較簡單的線性預(yù)測方法。 線性預(yù)測是取預(yù)測函數(shù)為各知信源符號的線性函數(shù)，即取 的預(yù)測值為： 其中 為預(yù)測系數(shù)。 21,rkrrsss rsrs12(,)rrrrksf sss ( )f21,rkrrsss rs1kririisa s ia 最簡單的預(yù)測是令 稱為前值預(yù)測，常用的差值預(yù)測就屬于這類。 利用預(yù)測值來編碼的方法可分為兩類：一類是對實踐值與預(yù)測值之差進展編碼，也叫差值預(yù)測編碼。另一類方法是根據(jù)差值的大小，決議能否需傳送該信源符號。例如，可規(guī)定某一閾值T，當(dāng)差值小于T時可不傳送，對于相關(guān)性很強的信源序列，常有

48、很長一串符號的差值可以不傳送，此時只需傳送這串符號的個數(shù)，這樣能大量緊縮碼率。這類方法普通是按信宿要求來設(shè)計的，也就是緊縮碼率引起的失真應(yīng)能滿足信宿需求。1rrss 下面簡單引見差值預(yù)測編碼系統(tǒng)。假設(shè)信源的相關(guān)性很強，那么采用差值編碼可得較高的緊縮率。由于相關(guān)性很強的信源可較準(zhǔn)確地預(yù)測待編碼的值，使得這個差值的方差將遠小于原來的信源取值，所以在同樣失真要求下，量化級數(shù)可大大減少，從而較顯著地緊縮碼率。 差值預(yù)測編碼系統(tǒng)的框圖如以下圖所示，在編碼端主要由一個符號編碼器和一個預(yù)測器組成，在解碼端主要由一個符號解碼器和一個預(yù)測器組成。編碼器解碼器 當(dāng)輸入信源序列逐個進入編碼器時，預(yù)測器根據(jù)假設(shè)干個過

49、去的輸入產(chǎn)生對當(dāng)前輸入像素的估計值。預(yù)測器的輸出舍入成最近的整數(shù)，并被用來計算預(yù)測誤差： 在解碼器中根據(jù)接納到的變長碼字重建 ，并執(zhí)行以下操作： 而 可經(jīng)過式 進展預(yù)測得到。rrress rerrrses rs 1kririisa s 差值編碼的特點： 在差值編碼中所能獲得的緊縮率與預(yù)測誤差序列所產(chǎn)生的熵的減少量直接有關(guān)。 經(jīng)過預(yù)測可消除相關(guān)，所以預(yù)測誤差的概率分布普通在零點附近有一個頂峰，并且與輸入信源分布相比其方差較小。5.4.4 變換編碼 由前節(jié)曾經(jīng)看到，對于有記憶信源，由于信源前后符號之間具有較強相關(guān)性，要提高信息傳輸?shù)男适紫刃枨蠼獬旁捶栔g的相關(guān)性，解除相關(guān)性可以在時域上進展如

50、前面引見的預(yù)測編碼方法，也可以在變換域上進展，這就是本節(jié)要引見的變換編碼方法。對于圖像信源等相關(guān)性更強的信源，常采用基于正交變換的變換編碼方法進展數(shù)據(jù)緊縮。 變換編碼的根本原理是將原來在空間時間域上描畫的信號，經(jīng)過一種數(shù)學(xué)變換例如傅里葉變換等，將信號變到變換域例如頻域等中進展描畫，在變換域中，變換系數(shù)之間的相關(guān)性經(jīng)常顯著下降，并常有能量集中于低頻或低序系數(shù)區(qū)域的特點，這樣就容易實現(xiàn)碼率的緊縮，并還可大大降低數(shù)據(jù)緊縮的難度。 最早將正交變換思想用于數(shù)據(jù)緊縮是在20世紀(jì)60年代末期，由于快速傅里葉變換的出現(xiàn)，人們開場將離散傅里葉變換用于圖像緊縮；之后在1969年哈達瑪變換用于圖像緊縮；1971年K

51、L變換用于圖像緊縮，得到了最正確的性能，故KL變換又稱為最優(yōu)變換；1974年出現(xiàn)了綜合性能較好的離散余弦變換DCT，并很快得到廣泛的運用；20世紀(jì)80年代后期，國際電信聯(lián)盟(ITU)制定的圖像緊縮規(guī)范H.261選定DCT作為中心的緊縮模塊；隨后國際規(guī)范化組織(ISO)制定的活動圖像緊縮規(guī)范MPEG-1也以DCT作為視頻緊縮的根本手段；更新的視頻緊縮國際規(guī)范中也有用到DCT。 下面我們首先引見變換編碼的根本原理，然后引見變換編碼中常用的幾種變換。 (1)變換編碼的根本原理 設(shè)信源延續(xù)發(fā)出的兩個信源符號 之間存在相關(guān)性，假設(shè)均為3比特量化，即它們各有八種能夠的取值，那么 之間的相關(guān)特性可用圖表示。

52、12,s s12,s s 圖中的橢圓區(qū)域表示s1與s2相關(guān)程度較高的區(qū)域，此相關(guān)區(qū)關(guān)于s1軸和s2軸對稱。顯然假設(shè)s1與s2的相關(guān)性越強，那么橢圓外形越扁長，而且變量s1與s2幅度取值相等的能夠性也越大，二者方差近似相等，即 。 假設(shè)我們將s1與s2的坐標(biāo)軸逆時針旋轉(zhuǎn)45，變成 平面，那么橢圓區(qū)域的長軸落在 軸上，此時當(dāng) 取值變動較大時， 所受影響很小，闡明 與 之間的相關(guān)性大大減弱。同時由圖可以看出：隨機變量 與 的能量分布也發(fā)生了很大的變化，在相關(guān)區(qū)域內(nèi)的大部分點上的 方差均大于的 方差，即 . 2212 12y Oy1y1y1y1y1y2y2y2y2y2212yy 另外，由于坐標(biāo)變換不會

53、使總能量發(fā)生變化，所以有： 由此可見，經(jīng)過上述坐標(biāo)變換，使變換后得到的新變量 、 呈現(xiàn)兩個重要的特點： 變量間相關(guān)性大大減弱； 能量更集中，即 ，且 小到幾乎可忽略. 這兩個特點正是變換編碼可以實現(xiàn)數(shù)據(jù)緊縮的重要根據(jù)。2212 2212yy 1y2y2212yy22y 上述坐標(biāo)旋轉(zhuǎn)對應(yīng)的變換方程為： 由于 因此，坐標(biāo)旋轉(zhuǎn)變換矩陣 是一個正交矩陣，由正交矩陣決議的變換稱為正交變換。1122cossinsincosysys cossincossin10sincossincos01T cossinsincosT 普通的變換編碼系統(tǒng)框圖如下圖 高性能的變換編碼方法不僅能使輸出的緊縮信源矢量中各分量之間

54、的相關(guān)性大大減弱，而且使能量集中到少數(shù)幾個分量上，在其他分量上數(shù)值很小，甚至為“0。因此在對變換后的分量(系數(shù))進展量化再編碼時，由于在量化后等于“0的系數(shù)可以不傳送，因此在一定保真度準(zhǔn)那么下可到達緊縮數(shù)據(jù)率的目的，量化參數(shù)的選取主要根據(jù)保真度要求或恢復(fù)信號的客觀評價效果來確定。 在變換編碼方法中最關(guān)鍵的是正交變換的選擇，最正確的正交變換是KL變換，這一變換的根本思想是由Karhunen和Loeve兩人分別于1947年和1948年單獨提出的，主要用于圖像信源的緊縮。由于KL變換使變換后隨機矢量的各分量之間完全獨立，因此它常作為衡量正交變換性能的規(guī)范，在評價其它變換的性能時，常與KL變換的結(jié)果進

55、展比較。 KL變換的最大缺陷是計算復(fù)雜，而且其變換矩陣與信源有關(guān)，適用性不強。為此人們又找出了各種適用化程度較高的變換，如離散傅里葉變換DFT、離散余弦變換DCT、沃爾什變換WHT等等，其中性能較接近KL變換的是離散余弦變換DCT，在某些情況下，DCT能獲得與KL變換一樣的性能，因此DCT也被稱為準(zhǔn)最正確變換。 (2)離散余弦變換 DCT是根據(jù)DFT的缺乏，按實踐需求而構(gòu)造的一種實數(shù)域的變換，由于DCT源于DFT，這里我們先調(diào)查DFT。 DFT是一種常見的正交變換，在數(shù)字信號處置中得到廣泛運用，離散傅里葉變換對定義為： 設(shè)長度為的離散序列為 ，DFT定義為： 正變換 反變換 其中: 將正變換寫成矩陣方式: 其中:T為離散傅里葉變換的變換矩陣。110011( )() exp2/=() (u0,1,2,.,N-1)NNuxxxF ufxjuxNfx WNN 110011()() exp2/ () 0,1,2,.,N -1NNuxuufxFujuxNFu WxNN 2 /ejNW ( )( )