有約束信道及其編碼

1、logo 第十章第十章 有約束信道及其編碼有約束信道及其編碼 http:/:4213/xxl/main.htm 信息論基礎(chǔ)信息論基礎(chǔ) logo 本章主要內(nèi)容 標號圖的性質(zhì)標號圖的性質(zhì)1 有約束信道容量有約束信道容量2 有約束序列的性質(zhì)有約束序列的性質(zhì)3 有約束信道編碼定理有約束信道編碼定理4 有約束序列編碼與應(yīng)用有約束序列編碼與應(yīng)用5 logo 摘要： v本章研究有約束信道編碼的基本理論與技術(shù)，主本章研究有約束信道編碼的基本理論與技術(shù)，主 要內(nèi)容按順序安排如下：介紹研究有約束信道的要內(nèi)容按順序安排如下：介紹研究有約束信道的 重要工具重要工具標號圖標號圖；引入有約束信道容量的概；引入有約束信道容

2、量的概 念并提出念并提出有約束信道容量的計算方法有約束信道容量的計算方法；研究游程；研究游程 長度受限序列、部分響應(yīng)最大似然序列和直流平長度受限序列、部分響應(yīng)最大似然序列和直流平 衡序列的性質(zhì)；介紹衡序列的性質(zhì)；介紹仙農(nóng)有約束信道的基本定理仙農(nóng)有約束信道的基本定理 和和有限狀態(tài)編碼定理有限狀態(tài)編碼定理；最后介紹重要的有約束編；最后介紹重要的有約束編 碼序列的實例及主要應(yīng)用。碼序列的實例及主要應(yīng)用。 logo 10.1 標號圖的性質(zhì) 標號圖的基本概念標號圖的基本概念 標號圖的變換標號圖的變換 logo 10.1.1 標號圖的基本概念標號圖的基本概念 ()e ee v一個標號圖（或有限標號圖）g由

3、一個有限 狀態(tài)集合(v=vg)）和一個有限邊集合 (e=eg)以及邊標號(l=lg: e ，其中 為有限字母表）組成，其中每條邊 都有一個初始狀態(tài)和一個終止狀態(tài)，這些 狀態(tài)都屬于。標號圖記為 g =（v，e，l） logo 相關(guān)概念及性質(zhì)相關(guān)概念及性質(zhì) v標號圖為標號圖為有向圖有向圖，每條邊只有一個方向，由起始，每條邊只有一個方向，由起始 狀態(tài)指向終止狀態(tài)，而且每條邊都和一個狀態(tài)指向終止狀態(tài)，而且每條邊都和一個標號標號相相 對應(yīng)。每條邊也是其初始狀態(tài)的對應(yīng)。每條邊也是其初始狀態(tài)的輸出邊輸出邊，同時又，同時又 是其終止狀態(tài)的是其終止狀態(tài)的輸入邊輸入邊。對于每個狀態(tài)，都允許。對于每個狀態(tài)，都允許

4、存在從自身起始并終止到自身的邊。這種邊稱做存在從自身起始并終止到自身的邊。這種邊稱做 自環(huán)自環(huán)。 v從給定狀態(tài)到某一狀態(tài)允許存在多條邊，但每條從給定狀態(tài)到某一狀態(tài)允許存在多條邊，但每條 邊要有邊要有不同不同的標號；而從一狀態(tài)到不同狀態(tài)的邊的標號；而從一狀態(tài)到不同狀態(tài)的邊 可以有相同的標號。為了用標號圖產(chǎn)生有限符號可以有相同的標號。為了用標號圖產(chǎn)生有限符號 序列，可沿圖中的選定的路徑依次讀出所經(jīng)過邊序列，可沿圖中的選定的路徑依次讀出所經(jīng)過邊 所對應(yīng)的標號，這就產(chǎn)生一串所對應(yīng)的標號，這就產(chǎn)生一串符號序列符號序列。 logo 1 23 a b c b c d 該圖有3個狀態(tài)1，2，3； 有限字母表為

5、 ； 圖中有6條邊，其中在狀態(tài)1 存在自環(huán)，從狀態(tài)3到狀態(tài)1 有兩條邊，但標號不同；而 從狀態(tài)3到狀態(tài)1和從狀態(tài)3到 狀態(tài)2有兩條相同標號（c） 的邊；沿路徑， 可產(chǎn)生序列為bbda。 , , , a b c d 12311 例例10.1.1 10.1.1 logo 有約束系統(tǒng)有約束系統(tǒng) v沿標號圖的所有路徑讀出的標號所產(chǎn)生的沿標號圖的所有路徑讀出的標號所產(chǎn)生的序列序列 （或（或字字）集合集合，稱為一個有約束系統(tǒng)，記為，稱為一個有約束系統(tǒng)，記為s s?？伞？?見一個給定的有約束系統(tǒng)可以用標號圖來表示。見一個給定的有約束系統(tǒng)可以用標號圖來表示。 v由于有約束系統(tǒng)只與標號有關(guān)而與標號圖的狀態(tài)由于有

6、約束系統(tǒng)只與標號有關(guān)而與標號圖的狀態(tài) 無關(guān)，所以同一個有約束系統(tǒng)可用多種不同的標無關(guān)，所以同一個有約束系統(tǒng)可用多種不同的標 號圖來表示。號圖來表示。 logo 連接矩陣連接矩陣 v由于標號圖是由于標號圖是有向圖有向圖，所以可以用，所以可以用連接矩陣連接矩陣來描來描 述。設(shè)一個述。設(shè)一個n n狀態(tài)的標號圖狀態(tài)的標號圖g g ，定義連接矩陣，定義連接矩陣dgdg （或簡記為（或簡記為d d）為）為 v n nn n 階矩陣：階矩陣： d=d i j i j （ 1011） 其中，其中，d dij ij為從狀態(tài) 為從狀態(tài)i i到狀態(tài)到狀態(tài)j j 的邊的數(shù)目，的邊的數(shù)目， i i，j =1j =1，n

7、 n。連接矩陣也稱鄰接矩陣。連接矩陣也稱鄰接矩陣。 例如，例例如，例10.1 10.1 中的標號圖的連接矩陣是中的標號圖的連接矩陣是： 110 001 210 d 1 23 a b c b c d logo n階連接矩陣階連接矩陣 v 設(shè)g是一個標號圖，g的n次冪用gn表示，也是一個狀態(tài)集 合與g相同的標號圖，而它的每條邊都與在g中產(chǎn)生的長度 為n的路徑相對應(yīng)。因此gn的每條邊對應(yīng)的標號就是一條 長度為n且滿足g的約束的序列。gn的連接矩陣dg就是dg的 n次冪dgn（或簡記為d dn n），即 （ 1012） 其中，每個元素表示在圖g中從狀態(tài)i經(jīng)n步到狀態(tài)j的路徑 數(shù)。實際上，它表示此有約束

8、系統(tǒng)從狀態(tài)i到狀態(tài)j所能構(gòu) 成的長度為n的序列的數(shù)目。 n nn gij g ddd logo 例例10.1.1 10.1.1 續(xù)續(xù) v 求例求例.1圖中的有約束系統(tǒng)圖中的有約束系統(tǒng), ,由狀態(tài)由狀態(tài)3 3到狀態(tài)到狀態(tài)2 2所能構(gòu)成所能構(gòu)成 的長度為的長度為3 3的序列的數(shù)目，并列出這些序列。的序列的數(shù)目，并列出這些序列。 1 23 a b c b c d 3 3 110321 001221 210432 d 解：計算解：計算 所求序列數(shù)為，這所求序列數(shù)為，這3 3個序列是：個序列是： cbccbc，dabdab，cabcab。 logo 10.1.2 10.1.2 標號圖

9、的變換標號圖的變換 等價狀態(tài)合并等價狀態(tài)合并 : 在標號圖中，狀態(tài)在標號圖中，狀態(tài)s s1 1,s,s2 2, , ,s sj j是等價的，當是等價的，當 且僅當對每一個可能的輸入序列，不管且僅當對每一個可能的輸入序列，不管 s s1 1,s,s2 2, , ,s sj j中哪一個是初始狀態(tài)，所產(chǎn)生的序列中哪一個是初始狀態(tài)，所產(chǎn)生的序列 完全相同。可以驗證，對于兩狀態(tài)完全相同?？梢则炞C，對于兩狀態(tài)s si i,s,sj j，如果它，如果它 們具有相同數(shù)目和對應(yīng)相同標號的輸出邊，并且們具有相同數(shù)目和對應(yīng)相同標號的輸出邊，并且 具有相同標號的邊的終止狀態(tài)也相同，那么具有相同標號的邊的終止狀態(tài)也相同

10、，那么s si i和和 s sj j是等價的。是等價的。 等價狀態(tài)滿足等價狀態(tài)滿足自反性自反性、對稱性對稱性和和傳遞性傳遞性。 logo 等價狀態(tài)可以等價狀態(tài)可以合并合并成一個狀態(tài)。例如，狀態(tài)成一個狀態(tài)。例如，狀態(tài)s si i具有輸具有輸 出邊集合出邊集合 e ei i1 1, ,e ei i2 2 ，狀態(tài)，狀態(tài)s sj j具有輸出邊集合具有輸出邊集合 e ej j1 1, ,e ej j2 2 ，并，并 且且e ei i1 1與與e ej j1 1有相同的標號和終止狀態(tài)，有相同的標號和終止狀態(tài)，e ei i2 2與與e ej j2 2有相同的標有相同的標 號和終止狀態(tài)，那么狀態(tài)號和終止狀態(tài)，

11、那么狀態(tài)s si i和和s sj j可以合并成一個狀態(tài)?？梢院喜⒊梢粋€狀態(tài)。 等價狀態(tài)合并后，原來兩狀態(tài)等價狀態(tài)合并后，原來兩狀態(tài)合并前的輸入邊都保留合并前的輸入邊都保留 作為合并后新狀態(tài)的輸入邊作為合并后新狀態(tài)的輸入邊，而，而只保留合并前其中一個狀只保留合并前其中一個狀 態(tài)的輸出邊態(tài)的輸出邊。等價狀態(tài)合并后的圖與合并前的圖是。等價狀態(tài)合并后的圖與合并前的圖是等價等價的。的。 即兩圖所產(chǎn)生的序列完全相同。等價狀態(tài)合并的示意圖如即兩圖所產(chǎn)生的序列完全相同。等價狀態(tài)合并的示意圖如 下圖所示。下圖所示。 logo 狀態(tài)節(jié)點的吸收狀態(tài)節(jié)點的吸收 如圖所示如圖所示, ,節(jié)點節(jié)點s s2 2可被可被吸收吸

12、收，從而變成新的標號圖。此，從而變成新的標號圖。此 時應(yīng)注意：時應(yīng)注意： 1 1、狀態(tài)節(jié)點被吸收后，圖的標號集合要擴展。例如，、狀態(tài)節(jié)點被吸收后，圖的標號集合要擴展。例如， 圖中的標號集合就增加圖中的標號集合就增加ba,caba,ca 等元素。等元素。 2 2、狀態(tài)節(jié)點被吸收后，標號圖與原來的圖不等價。因、狀態(tài)節(jié)點被吸收后，標號圖與原來的圖不等價。因 此，僅當所研究的問題與有約束序列的起點無關(guān)時才能使此，僅當所研究的問題與有約束序列的起點無關(guān)時才能使 用該方法。用該方法。 s1 s3 s4 s1 s4 s3 s2 a ca ba c b (a) (b) logo 例例10.1.2 10.1.2

13、 在摩爾斯電碼中，容許的符號有3個，分別為“點”、 “劃”、“空”，規(guī)定不能出現(xiàn)3個連續(xù)的“空”。試畫出摩 爾斯電碼所對應(yīng)的狀態(tài)圖。 點 空空空 劃 劃 點 空 空劃 劃 點 空 點 劃 解： 將“點”、“劃”、“空”、 “空空”作為圖的4個狀態(tài)，由題 意，“空空”后面不能接“空”。 所求狀態(tài)圖如圖所示。圖中, 狀態(tài) 集合v=點，劃，空，空空，邊標 號集合=點，劃，空。 logo 利用等價狀態(tài)關(guān)系對上狀態(tài)圖化簡利用等價狀態(tài)關(guān)系對上狀態(tài)圖化簡 解： 合并等價節(jié)點合并等價節(jié)點 狀態(tài)節(jié)點吸收狀態(tài)節(jié)點吸收 點 劃 空 空 空 劃 劃 點 點 空 點 空 劃 點 劃 空 劃 劃 點 點 空 空 點 空

14、劃 （a） 點劃 （b） 劃 空 點 空劃 空 空 點 空 空 劃 點 例例10.1.2 10.1.2 續(xù)續(xù) logo 10.2 有約束信道容量有約束信道容量 logo 一個有約束信道的容量c定義為： 其中，m（t）為時間長度t內(nèi)所允許的序列的個數(shù)。這 些不同排列構(gòu)成的序列可以代表信源的不同輸出。根據(jù)漸 近均分特性，當t足夠大時，信源輸出序列接近等概率出 現(xiàn)；再根據(jù)離散最大熵定理，當這m（t）種序列等概率時， 達到最大熵。所以，上式表示在單位時間內(nèi)所能傳輸?shù)淖?大信息量。 10.2.1 10.2.1 有約束信道容量的定義有約束信道容量的定義 log( ) lim t m t c t logo

15、為使傳送的消息適應(yīng)信道的特性或與檢測所采用的信 號處理方式相匹配，傳輸系統(tǒng)將某些約束加到傳輸序列上， 這個過程就是對有約束序列進行編碼的過程。 我們將產(chǎn)生有約束序列的系統(tǒng)稱為有約束系統(tǒng)。因此 信道傳送有約束的消息和系統(tǒng)按照某種約束產(chǎn)生消息實際 的效果是一樣的，所以有約束系統(tǒng)和有約束信道具有相同 的含義。實際上，這種有約束信道與信源問題沒有多大差 別。如果我們把受信道規(guī)則約束的符號看成受同樣規(guī)則約 束的信源符號，那么信道符號間的約束相當于信源符號之 間的相關(guān)性，所以計算信源的最大熵與計算這種信道的容 量是等價的。 logo 定理 ：等時長有約束信道的容量等于系統(tǒng)連接矩陣最大特 征值的對數(shù)，即 c

16、=log2 max (比特/符號） 其中， max為系統(tǒng)連接矩陣最大特征值。 證明： （見教材） logo v 設(shè)一個有約束系統(tǒng)的標號圖。如圖所示，其中0,1符號等 時長,寫出系統(tǒng)的連接矩陣和特征方程，并求d=1時有約束 信道的容量。 v 解： v 令d=1則 （*） v 得： v 信道容量 v 令 得 （比特/符號） 1 1 000 d+ +1 d2 0 0100 0010 001 101 d 0dz i 1 10 dd zz 2 10zz max (15)/2 2max2 loglog (15)/20.694c 例例10.2.1 10.2.1 logo 特征方程：特征方程： v 設(shè)信源符號

17、 的時間長度分別為 ，其 中每個是某單位時長的整數(shù)倍，方程 稱為系統(tǒng)的特征方程。 定理定理10102 21 1：等時長有約束信道的容量等于系統(tǒng)連接矩陣 最大特征值的對數(shù)。 c=log2 max (比特/符號） 10.2.3 10.2.3 不等時長符號無約束信道的容量不等時長符號無約束信道的容量 12 , n a aa 12 , , n t tt 12 1 n ttt zzz logo 在摩爾斯電碼中，在摩爾斯電碼中，“點點”、“劃劃”、“空空”，的時間，的時間 長度分別為（其中為單位時長），求無約束信道的容量。長度分別為（其中為單位時長），求無約束信道的容量。 解 列出特征方程為 求解可得 ，

18、 比特 信道容量 比特/單位時長 000 243 1 ttt zzz 0 1.466 t x 0 2 log ()0.565 t x 0 20 log ()/0.565 t cxt 例例10.2.2 10.2.2 logo v 將前例中的標號圖化簡成一個狀態(tài)，然后求無約束信道的 容量。 解解 將例10. 2. 2中的標號圖中的1，2，d狀態(tài)節(jié)點吸收 可得到如圖所示 所對應(yīng)的特征方程為 與（*）式完全相同。 故所求結(jié)果與例10. 2. 1相同。 0 1 0 0 d個“0” d+ +1 (1)1 10 d zz 例例10.2.2 10.2.2 續(xù)續(xù) logo 定理定理10. 2. 310. 2.

19、3 v 設(shè) 為所允許的從狀態(tài)i到狀態(tài)j的第s符號的時長,則信 道容量 為下面方程的最大實根： 其中, 證明：（參見教材） 10.2.4 10.2.4 不等時長符號有約束信道的容量不等時長符號有約束信道的容量 ( )s ij l logc ( ) 0 s ij l ij s 1 0 ij ij ij logo 定理10.2.3可以把定理10.2.1與定理10.2.2兩種情況作為 特例來處理。 例如，當?shù)葧r長符號時，設(shè) ，方程 變?yōu)?，這與 等價。 對于無約束情況， 中相當于只含一項，而 包含了所有符號的時長，這歸結(jié)于 ( ) 1 s ij l ( ) 0 s ij l ij s 1 0 ijij

20、 d 0dz i ( ) 0 s ij l ij s ( )s ij l 12 1 n ttt zzz logo v 在例10.2.2中引入兩個“空”后不能再接“空”的約束，求信 道容量。 解：記 =“空空”， =“空”， =“點劃”，則有 代入方程 ，得 展開得 求解可得： 信道容量 點 劃 空 空 空 劃 劃 點 點 空 點 空 劃 1 s 2 s 3 s 1 130 2lt 2 130 4lt 210 3lt 1 230 2lt 2 230 4lt 320 3lt 1 330 2lt 2 330 4lt ( ) 0 s ij l ij s 00 000 000 24 324 324 10

21、 10 01 tt ttt ttt 000000 1087542 1 tttttt 0 1.453 t 0 20 log ()/0.539 t ct 例例10.2.2 10.2.2 續(xù)續(xù)2 2 logo 10.3 有約束序列的性質(zhì)有約束序列的性質(zhì) logo 10.3.1 10.3.1 信道對傳輸序列的約束信道對傳輸序列的約束 信道的約束通常可以分為信道的約束通?？梢苑譃闀r域時域約束和約束和頻域頻域約束。約束。 時域約束時域約束： 對于采用對于采用峰值檢測技術(shù)峰值檢測技術(shù)的系統(tǒng)，要求在傳輸二電平符號的系統(tǒng)，要求在傳輸二電平符號 序列中兩個序列中兩個“1”1”（高電平）符號之間的（高電平）符號之間

22、的“0”0”游程的長度不游程的長度不 能太小，以減小碼間干擾；也不能太大，以利于同步信息的能太小，以減小碼間干擾；也不能太大，以利于同步信息的 提取。與這類要求對應(yīng)的編碼是提取。與這類要求對應(yīng)的編碼是游程長度受限游程長度受限（rllrll）碼。）碼。 對于對于采用部分響應(yīng)最大似然檢測技術(shù)采用部分響應(yīng)最大似然檢測技術(shù)的系統(tǒng)，不但要求的系統(tǒng)，不但要求 數(shù)據(jù)序列中兩個數(shù)據(jù)序列中兩個“1”1”符號之間的符號之間的“0”0”游程不能太長（以利游程不能太長（以利 于同步信息的提取和增益控制），而且還要求序列的奇偶交于同步信息的提取和增益控制），而且還要求序列的奇偶交 織子序列中的織子序列中的“0”0”游程

23、也不能太長（以減小記憶長度防止游程也不能太長（以減小記憶長度防止 惡性差錯傳播）。與這類要求對應(yīng)的編碼是惡性差錯傳播）。與這類要求對應(yīng)的編碼是部分響應(yīng)最大似部分響應(yīng)最大似 然然（prmlprml）序列編碼。）序列編碼。 以上兩種約束都是時域約束。以上兩種約束都是時域約束。 logo 頻域約束頻域約束： v 頻域約束指的是，要求傳輸?shù)男蛄袧M足一定的頻譜特頻域約束指的是，要求傳輸?shù)男蛄袧M足一定的頻譜特 性，以便與信道的頻譜特性相匹配或減小對系統(tǒng)某些頻率性，以便與信道的頻譜特性相匹配或減小對系統(tǒng)某些頻率 范圍的干擾。例如，要求序列不含某一個特殊頻率，這就范圍的干擾。例如，要求序列不含某一個特殊頻率，

24、這就 是是頻譜零點限制頻譜零點限制。在大多數(shù)情況下要求傳輸?shù)男蛄胁缓?。在大多?shù)情況下要求傳輸?shù)男蛄胁缓?流。這種序列稱為流。這種序列稱為無直流序列無直流序列或直流平衡序列?；蛑绷髌胶庑蛄小?v 本節(jié)所介紹的游程受限序列和部分響應(yīng)最大似然序列本節(jié)所介紹的游程受限序列和部分響應(yīng)最大似然序列 都是時域受限序列，它們的信道容量計算和編譯碼器的設(shè)都是時域受限序列，它們的信道容量計算和編譯碼器的設(shè) 計方法都是類似的。計方法都是類似的。 logo 在rll序列中規(guī)定了符號游程的最小和最大長度。因為rll序列與 稱做（d，k）序列有密切關(guān)系。我們先介紹（d，k）序列。 （d d，k k）序列：）序列： 一

25、個（d，k）受限序列，簡稱（d，k）序列，同時 滿足下列兩個條件： v d d約束約束 兩個邏輯“1”被長度至少為d的“0”游程所 分隔； v k k約束約束 “0”游程的最大長度為k。 v 如果僅滿足（1），則稱d受限（k= ），并稱為d序列。 logo （d d，k k）序列的容量）序列的容量 一個（d，k）序列的標號圖如圖所示： 設(shè) 為（d，k）序列連接矩陣 ，則d為 矩陣，且 將上圖化簡，只剩下狀態(tài)1，則圖中所包含的符號長 度分別為d+1，k，k+1，可以證明，此（d，k）序列 的特征方程為： （d，k）序列的容量也由c=log2 max確定 k+ +1d+ +2 2d+ +121 d

26、 00000 111 1 1,1 1,1,1 0, i ij ij did djiik d 其它 ij dd(1)(1)kk (1)(1) 1 kkd zzz logo 在實際應(yīng)用中，rll序列通常按如下步驟產(chǎn)生： v 首先按rll序列的要求產(chǎn)生（d，k）序列， v 再將（d，k）序列變成nrzi碼，從而構(gòu)成rll序列。 v nrzi（non-return to zero-inverted）碼，實際上是一種差分編碼。 設(shè) 分別為編碼器的輸入、輸出與狀態(tài)序列，nrzi編碼器的運 算關(guān)系如下： 其中， 為初態(tài)，可預(yù)先給定。 , kkk a b s 1kkk sas 1,1 1,0 k k k s

27、b s 0 s logo 已知一（d，k）序列為 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 ， 求對應(yīng)的nrzi碼，設(shè)編碼器初態(tài)為1。 k = 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 k = 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 1 k = 1 1 -1 -1 -1 -1 1 1 1 -1 -1- 1 -1 1 -1 -1 1 # 很容易證明，由d，k序列轉(zhuǎn)換成的rll 序列的游程最小 長度和最大長度分別為d+1和k+1。在本例中，（d，k）=（0， 3），所以在輸出的nrzi碼序列中，最短的同符號游程長度為 2，最大的同

28、符號游程長度為4。 a s b 例例10.3.1 10.3.1 logo nrzi編碼器 nrzi編碼器可用狀態(tài)轉(zhuǎn)移圖或網(wǎng)格圖來描述， 狀態(tài)轉(zhuǎn)移圖 網(wǎng)格圖 圖中，編碼器有兩個狀態(tài)、4條邊，每條邊標號的左右兩部分分別 表示在該邊的起始狀態(tài)下編碼器的輸入與輸出。例如，在狀態(tài)0，當輸 入為1時輸出為+1，然后轉(zhuǎn)到狀態(tài)1。 logo 10.3.3 10.3.3 部分響應(yīng)最大似然（部分響應(yīng)最大似然（prmlprml）序列）序列 v 在采用部分響應(yīng)最大似然檢測技術(shù)的系統(tǒng)中，約束通常用 兩個參數(shù)g和i來描述，其中，g是數(shù)據(jù)序列中所允許的“0” 游程的最大長度，i是序列的奇偶交織子序列中所允許的 “0”游程的

29、最大長度。我們用(0,g/i)來表示這種有約束 序列，其中的“0”可以看成（d，k）約束中的d，且d=0， 而g和i類似于k約束。 logo prml系統(tǒng)的標號圖 v 為描述prml約束，定義3個參數(shù)：g，a，b。其中g(shù)表示從序 列的某時刻t到此前最后一個“1”之間序列中“0”的個數(shù)， 而a和b分別表示從時刻t-1和t到此前各自所在奇、偶子序列 中最后一個“1”之間 “0”的個數(shù)。 v g是a和b的函數(shù)，可得到函數(shù)關(guān)系為： v 如果把表示序列的在某時刻狀態(tài)的值，還可以得到如下的狀 態(tài)轉(zhuǎn)移關(guān)系：設(shè)（0，g/i）約束的狀態(tài)集合為v，其中 且 狀態(tài)轉(zhuǎn)移規(guī)則如下： 序列輸出“0”： ，如果 序列輸出“

30、1”： 21() ( , ) 2() aab g a b bab ( , ):0,va ba bi ( , )g a bg ( , )( ,1)a bb a ( ,1)b av ( , )( ,0)a bb logo 求（求（0 0，g/ig/i）= =（0 0，3/33/3）約束系統(tǒng)的連接矩陣）約束系統(tǒng)的連接矩陣 解 根據(jù)a，b的允許范圍以及等時長約束系統(tǒng)條件計算結(jié)果 如下： 允許的狀態(tài)有12個，按字典順序排列如下： a a0 00 00 00 01 11 11 11 12 22 22 22 23 33 33 33 3 b b0 01 12 23 30 01 12 23 30 01 12 2

31、3 30 01 12 23 3 g(a,bg(a,b) )0 01 11 11 10 02 23 33 30 02 24 44 40 02 24 46 6 (0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1),(3,0),(3,1) 例例10.3.2 10.3.2 logo 得到連接矩陣為： 110000000000 000011000000 000000001100 000000000011 101000000000 000010100000 000000001000 000000000010 100100000000 000

32、010010000 100000000000 000010000000 d 例例10.3.2 10.3.2 續(xù)續(xù) logo prml系統(tǒng)的容量 v 與一般有約束系統(tǒng)一樣，根據(jù)連接矩陣，可以求得信道容 量。（0，g/i）序列的編碼器可以用與（d，k）序列的相 同的方法來設(shè)計。 例1032（續(xù)）求（0，g/i）=（0，3/3）約束系統(tǒng)的容量 v 解：通過計算，求得連接矩陣的最大特征值為 ， 容量 比特/符號 max 1.8865 2max log0.9157c logo 10.3.4 10.3.4 直流平衡序列直流平衡序列 v 直流平衡序列也稱無直流序列，即在零頻具有頻譜零點的 二進序列。這種序列

33、有利于過濾低頻干擾。 直流平衡序列的特性直流平衡序列的特性： 定義這個n狀態(tài)系統(tǒng)的連接矩陣dn。設(shè)dn的元素為dn(i,j) ，那么如果從狀態(tài)i允許轉(zhuǎn)移到狀態(tài)j，則dn(i,j)=1，否則 為0。 則序列有以下特征： 其它 可見，dn是一個對稱的toeplitz矩陣。此矩陣對應(yīng)一個具有反射 壁的隨機游動問題。此矩陣主對角線上元素是0，與其相鄰的上下對 角線元素是1，其余元素都是0。 (1, )( ,1)1 nn diidi i1,2,1in ( , )0 n di j logo 寫出寫出n=5n=5時的矩陣時的矩陣d dn n，并畫出狀態(tài)轉(zhuǎn)移圖。，并畫出狀態(tài)轉(zhuǎn)移圖。 解 狀態(tài)轉(zhuǎn)移矩陣 米里型和

34、等價的摩爾型狀態(tài)轉(zhuǎn)移圖 5 01000 10100 01010 00101 00010 d + +1 - -1- -1- -1- -1 + +1+ +1+ +1 + +1+ +1+ +1+ +1 - -1- -1- -1 - -1 例例10.3.3 10.3.3 logo 直流平衡序列的容量直流平衡序列的容量 v 我們知道，有約束信道的容量為連接矩陣最大特征值的對數(shù)。 現(xiàn)求直流平衡序列的容量。 設(shè) 為dn的特征多項式，可容易地計算： ， ， ， 對于n 2，可導(dǎo)出遞推關(guān)系 可以證明，此約束信道的容量為 )det nn zzid（ 1 ) zz（ 2 2 )1zz（ 3 3 )2zzz（ 42

35、4 )31zzz（ 12 )( )( ),3,4, nnn zzzzn （ 2max2 ()loglog 2cos,3 1 c nn n logo 求直流平衡序列的滑動數(shù)字和變化分別為n=3、4和10情況 下的容量。 v 解 比特/符號 比特/符號 比特/符號 當n增大時，容量也增大，當時，容量接近1比特/符號； 而且當n值較小時，容量的變化對n值比較敏感；但當當n 值較大時，容量的變化對n值不敏感。 2 (3)log 2cos /(3 1)0.5c 2 (4)log 2cos /(4 1)0.6942c 2 (10)log 2cos /(10 1)0.9403c 例例10.3.4 10.3.

36、4 logo 10.3.5 10.3.5 其它頻域受限序列其它頻域受限序列 v 除直流平衡序列外，根據(jù)實際需要還有其它類型的頻 域受限序列。例如，高階譜零點序列、零頻外的譜零點序 列以及無直流游程長度受限序列等。 v 直流平衡序列雖然簡單，但是對低頻分量的抑制量還 不太大。如果編碼序列的頻譜在零頻處的二階導(dǎo)數(shù)也為零， 那么就會提供對低頻分量的較大的抑制效果。具有這種性 質(zhì)的序列稱為dc2平衡序列。 v 設(shè)rdds為滑動數(shù)據(jù)和（rds）的和，可以證明，當rds 和rdds都有界時，序列頻譜在零頻有零點，頻譜二階導(dǎo)數(shù) 在零頻也有零點。如果序列的頻譜在零頻處的更高階導(dǎo)數(shù) 也為零，稱為高階譜零點序列。

37、 v 如果一個游程受限序列且滑動數(shù)據(jù)和有界，則稱無直流游 程受限序列（dcrll）。這種序列用三個參數(shù)來描述：d， k，n，其中d，k為（d，k）序列參數(shù)，n為數(shù)據(jù)和的變化。 logo 10.4 有約束信道編碼定理有約束信道編碼定理 logo 10.4.1 10.4.1 編碼器的描述編碼器的描述 編碼器可用一個常規(guī)的有限狀態(tài)時序機來描述。 它有1個p比特的輸入，1個q比特的輸出，內(nèi)部狀 態(tài)是時間k的函數(shù)。 編碼器輸出的碼字是輸入和狀態(tài)的函數(shù)。 編碼器由3個集合和兩個函數(shù)來描述：輸入、輸出 和狀態(tài)集合以及輸出函數(shù)和次態(tài)函數(shù)。 logo 編碼器框圖 圖10.4.1 編碼器框圖 h(s k,bk)

38、f(s k,xk) p比特 q比特 xk bk sk sk logo v輸入集合b，是一個p比特序列集合，通常b中元 素的個數(shù)|b|= =m，在時刻 k的輸入為 ； v狀態(tài)集合 ，設(shè)狀態(tài)數(shù)為有限，| |=n，在時 刻k的狀態(tài)為 ； v輸出集合x，是一個q比特碼字，所以|x| nm， 第k時刻的輸出用表示； v輸出函數(shù)h表示輸出對輸入與狀態(tài)的依賴關(guān)系： （10. 4. 1） v次態(tài)函數(shù)g規(guī)定了編碼器在處理一個信源字以后 所處的狀態(tài)，是當前狀態(tài)和輸出的函數(shù)，即 （10. 4. 2） (,) kkk xh s b 1 (,) kkk sg sx k s k b 2p logo 10.4.2 10.4

39、.2 編碼器性能指標編碼器性能指標 對編碼器的要求： v 較高的編碼效率 v 較低的復(fù)雜度 v 避免差錯傳播 logo v編碼器效率定義： 碼率和有約束信道容量之比，即 根據(jù)定理10.3.3，總是小于或等于1。我們總是希 望越大越好。不過，效率的提高往往以增加編碼 復(fù)雜度為代價。 /r c logo v為保證編碼器有較低的復(fù)雜度，應(yīng)該使在實現(xiàn)一 定碼率條件下，碼長盡量短。在碼率不變的條件 下可采用變長碼或采用合并原則來減小平均碼長。 v衡量編碼優(yōu)劣的另一項指標就是差錯傳播。一個 好的編碼應(yīng)使差錯傳播控制在盡量小的范圍內(nèi)。 在譯碼時可分成兩種譯碼方法，一是獨立狀態(tài)的 譯碼，二是依賴于狀態(tài)的譯碼。

40、獨立狀態(tài)的譯碼 往往具有較少的差錯傳播，而依賴于狀態(tài)的譯碼 往往容易產(chǎn)生差錯傳播。但這種方式又能使平均 碼長減小。因此，在選擇編碼方式時，要根據(jù)實 際對各項指標進行權(quán)衡。 logo v對于例1022中系統(tǒng)能否實現(xiàn)碼率為8/9的編碼 器？如果能實現(xiàn)，求編碼器的編碼效率。 v解 因為 （系統(tǒng)容量），所以能夠?qū)?現(xiàn)碼率為8/9的編碼器。 v編碼效率： 8/9 0.9157 (8/9)/0.915797.0% 例例10.4.1 10.4.1 logo v定理10.4.1 設(shè)一信源具有熵h(比特/符號),一信道具有容 量c(比特/秒),那么將信源編碼后以c/h- (符號/ 秒)的平均速率通過信道傳輸是可

41、能的,其中 可 以任意小,而以大于 的平均速率傳輸是不可能 的。(證明略) /c h logo v 定理10.3.2 設(shè)s為一個有約束系統(tǒng)，為一正整數(shù)，如果 p/q cr(s) （10.4.4） 則存在著碼率為p/q的有限狀態(tài)編碼器 (s,r)，其中， cr(s)為以為底的有約束系統(tǒng)的容量。（證明略） v 該定理在以下方面改進了仙農(nóng)的結(jié)果： （1）根據(jù)狀態(tài)分裂算法，給出了定理構(gòu)造性的證明； （2）當容量為有理數(shù)時，存在碼率等于信道容量的編 碼； （3）對于滿足不等式的任何正整數(shù)p、q，都存在碼率 為p/q的編碼器；特別是，當p、q互素時，可以設(shè)計碼率 為p/q的最小碼長為q的編碼器； logo

42、 注： v（1）通常使用的是二元信源， ，容量 c的 單位為比特/符號； v（2）今后所說的存在某種有約束信道編碼就是指 存在無差錯恢復(fù)的編碼。 2r logo v對于例1013中d=1條件的信道，是否存在碼率 分別為3/5，3/4的編碼？ v解 根據(jù)例1013的計算，信道容量 比特符號， ，存在有約束編碼， 而 ，不存在有約束編碼。 0.694c 3/5 0.6 0.694 3/40.750.694 例例10.4.2 10.4.2 logo 10.5 有約束序列編碼與應(yīng)用有約束序列編碼與應(yīng)用 logo v如果編碼器的標號圖只含一個狀態(tài)，那么就稱塊 編碼器。這是一種最簡單的編碼器類型。 v塊編

43、碼器可分為定長塊碼和變長塊碼編碼器。 logo 定長（定長（d d，k k）塊碼）塊碼 v定長（d，k）塊碼就是將信源序列分成長度為p的 信源字，再按照編碼規(guī)則將每個信源字映射成q個 信道符號所構(gòu)成的碼字。 一個r=3/5（1， ）的塊編碼器的信源字與碼字 的關(guān)系如表10. 5. 1所示。 v編碼效率 /10.6/0.6940.86r c （， ） 例例.1 logo 變長（d，k）塊碼實際上是固定速率變長碼。 在這種編碼中，信源字的長度不全相同，所對應(yīng) 的碼字的長度也不全相同，但保持相同的碼率。 因為要將信源序列分成長度不完全相同的碼字， 而且要求這種劃分具有唯一性。因此

44、信源字要滿 足異前置性，以保證唯一可編。同樣碼字也要滿 足異前置性，以保證唯一可譯。 logo v一個固定速率變長（2，7）碼（也稱franaszek 碼），編碼如表10. 5. 2所示，求碼率和編碼效 率。 例例10.5.2 10.5.2 logo v碼率 r=2/4=3/6=1/2。 因為d=2，k=7，代入（10. 3. 2）式，得 v解得 v信道容量 比特/符號 v編碼效率 v 通常固定速率變長（d，k）碼要比同碼率的 等長（d，k）碼的碼長小得多，從而編碼復(fù)雜度 也小得多。 876543 1zzzzzz max 1.4373 2max log0.5174c /0.5/0.5174 9

45、6.6%r c logo 10.5.2 10.5.2 實用直流平衡序列實用直流平衡序列 v直流平衡序列不是有限類型約束序列，而屬于所 謂幾乎有限類型序列。所以前面所介紹的編碼器 的設(shè)計方法對這種序列不適用。 v對低頻分量進行抑制的編碼系統(tǒng)大部分可用分組 碼實現(xiàn)，通過限制每個碼字中的正、負脈沖符號 的不平衡來實現(xiàn)對低頻或零頻分量進行抑制。下 面，我們引入差異的概念。 v一個碼字的差異是指這個碼字中“1”符號超過 “0”符號的個數(shù)。通常有3種構(gòu)造直流平衡序列 的方法：1）零差異碼，2）低差異碼，3）極性比 特碼。 logo 零差異編碼系統(tǒng)零差異編碼系統(tǒng) 在零差異編碼中，每個信源字唯一地用包含相同數(shù)

46、目 “1”和“0”的碼字來代表。很明顯，碼長應(yīng)為偶數(shù)。 設(shè)碼長為n，那么碼字的個數(shù)為 （1051） v（1051）式表示從n中選擇n/2個元素的組合數(shù)。碼 率為 比特/符號 （1052） v這種碼的特點是：1）各碼字的組合無需合并原則；2） 實際使用的碼字數(shù)為2的冪，比（1051）式表示的 數(shù)目少，所以使有效碼率降低；3）信源字與碼字有一 一對應(yīng)的關(guān)系。 0 /2 n n n 20 (1/) logrnn logo 低差異編碼系統(tǒng)低差異編碼系統(tǒng) 這種編碼系統(tǒng)除使用零差異碼字之外，還使用 非零差異碼字。其中給一部分信源字一一對應(yīng) 地分配零差異碼字，而在另一部分信源字中， 一個信源字用兩個碼字來表

47、示，并且這兩個碼 字有數(shù)值相等但符號相反的差異。在新碼字傳 輸前，根據(jù)滑動數(shù)字和的極性來選擇要傳輸?shù)?碼字。原則就是，在新碼字傳輸后使滑動數(shù)字 和的絕對值最小。同時在譯碼時要考慮狀態(tài)獨 立以防止差錯傳播。 logo v設(shè)由雙極性符號組成的碼字的碼長為n，n為偶數(shù)， 在一個碼字范圍內(nèi)的差異為d，即 v （1053） v這種碼的碼書由兩個集合 組成，其中，包含 零差異和正差異碼字，而 包含零差異和負差異 碼字。設(shè) 包含k+1個子集： ， ， 其中，子集 中的元素是所有可能的差異為2j 的碼字。 中的碼字是與 中碼字符號完 全相反的碼字。 1 n i i dx ,ss s s s 01 , k ss

48、s(/2)kn j s (0)jk s s logo 子集sj中元素的個數(shù)nj為 v （1054） v 在 或 中，總有效碼字數(shù)m為 （1055） 碼率為 （1056） v 這種碼的特點是：（1）與零差異編碼相比，有更多的碼 字可用，所以使有效碼率增大；（2）序列的低頻功率有 所增加。 ,0 /2 j n njk nj ss 0 k j j mssn 2 (1/ )logrnm logo 極性比特碼 v在這種編碼中，每個n長的碼字的前n-1位是信息符號， 最后一位為“極性比特”，通常置為“1”。 如果在開 始傳送新的n位碼字之前的積累差異與這個新的n位碼字 的差異符號相同，那么就將這個n位碼字的符號都變反， 否則碼字的符號不變，如果碼字的差異為零，則以1/2 的概率變反。 v該碼碼率為 （1057） v這種編碼的主要優(yōu)點是，編譯碼不用查表。 1 1/rn logo （d d，k k）塊碼編碼系統(tǒng)）塊碼編碼系統(tǒng) v（1）碼率4/5 gcr碼 vgcr(group coded recording)碼也叫“4/5碼”