第3講信源模型

1、 第3講 信源模型信源（information source），也稱消息源，是通信系統(tǒng)中發(fā)送消息的一方。信源所產(chǎn)生或者輸出的消息（message）是一個(gè)符號(hào)序列。任何產(chǎn)生符號(hào)序列的事物都可視為信源。報(bào)社、廣播電臺(tái)是信源；一個(gè)的人表情、行為是信源；我們所說的漢語是一個(gè)信源；一本英文小說也構(gòu)成一個(gè)信源；水面波紋、天空的云等等萬事萬物都是信源，都在傳遞著各自的信息。這一講我們介紹離散信源的幾種基本的和常用的模型。1. 隨機(jī)過程隨機(jī)過程是一個(gè)帶時(shí)間參數(shù)的隨機(jī)變量，其取值的統(tǒng)計(jì)特性可隨時(shí)間不斷變化，用以機(jī)變量描述狀態(tài)不斷變化的物理系統(tǒng)或者隨機(jī)現(xiàn)象。定義1.1 隨機(jī)過程是定義在同一個(gè)樣本空間上一族隨機(jī)變量

2、，其中t為時(shí)間參數(shù)，T是參數(shù)集合。對(duì)于任何，隨機(jī)變量的值稱為隨機(jī)過程在時(shí)刻t的狀態(tài)。為表達(dá)方便，可將隨機(jī)過程簡記為。定義1.2 當(dāng)隨機(jī)過程的參數(shù)集合為實(shí)數(shù)區(qū)間時(shí)，該隨機(jī)過程稱為時(shí)間連續(xù)的。當(dāng)隨機(jī)過程的參數(shù)集合為整數(shù)集或者非負(fù)整數(shù)集時(shí)，該隨機(jī)過程稱為時(shí)間離散的。時(shí)間離散的隨機(jī)過程稱為隨機(jī)序列。若X為隨機(jī)序列，則X在時(shí)刻t的狀態(tài)X(t)一般記為Xn。實(shí)例：熱噪聲電壓的樣本函數(shù) 這里我們主要學(xué)習(xí)關(guān)于隨機(jī)序列的基本概念和性質(zhì)，隨機(jī)過程的更多知識(shí)在后面需要的地方再作介紹。隨機(jī)序列的概率分布：隨機(jī)序列的統(tǒng)計(jì)特性用其中各隨機(jī)變量的概率分布和聯(lián)合概率分布進(jìn)行描述。一維分布：對(duì)于 這是隨機(jī)序列在時(shí)刻t處于狀態(tài)x

3、的概率。二維分布：對(duì)于任何狀態(tài)與，隨機(jī)序列從t時(shí)刻開始所經(jīng)歷的狀態(tài)序列為的概率記為 則函數(shù)稱為該隨機(jī)序列在t時(shí)刻的二維分布。n維分布：t時(shí)刻的n維分布定義為，對(duì)于任何狀態(tài)序列， 其中事件表示隨機(jī)序列從t時(shí)刻開始所連續(xù)經(jīng)歷的狀態(tài)為。記號(hào)：我們將隨機(jī)序列X在t時(shí)刻的n維分布也記為 初始分布：對(duì)于任何正整數(shù)n，初始時(shí)刻的n維分布稱為初始分布。高維分布蘊(yùn)含低維分布由t時(shí)刻的n維分布可以確定t時(shí)刻的(n-1)維分布，即 因此，由t時(shí)刻的n維分布可以確定t時(shí)刻的所有低維分布。隨機(jī)序列的平穩(wěn)性定義1.3 若隨機(jī)序列各時(shí)刻的n維分布相同，即對(duì)于任何n維狀態(tài)序列和任何時(shí)刻t，有 則稱該隨機(jī)序列是n維平穩(wěn)的。若對(duì)

4、于任何正整數(shù)n，隨機(jī)序列都是n維平穩(wěn)的，則稱該隨機(jī)序列為平穩(wěn)的（stationary）。平穩(wěn)隨機(jī)序列的n維分布記為或者。定義1.4 若隨機(jī)序列中各隨機(jī)變量是相互獨(dú)立并且具有相同的概率分布，則稱該隨機(jī)序列為獨(dú)立同分布的，記為i.i.d.。獨(dú)立同分布序列是最簡單的一類隨機(jī)序列。獨(dú)立同分布序列是平穩(wěn)的：（1） 由同分布性可得，對(duì)于任何時(shí)刻t和任何狀態(tài)x，有 等價(jià)地， （2） 由相互獨(dú)立性可得，對(duì)于任何時(shí)刻和任何狀態(tài)序列，有 再由（1）可得， 從而有 2. 波形信源與離散信源波形信源使用波形信號(hào)，例如電磁波的信號(hào)，調(diào)頻電磁波的信號(hào)是其不同的頻率，調(diào)幅電磁波的信號(hào)是不同的振幅。這些信號(hào)是在一段連續(xù)時(shí)間內(nèi)

5、高低連續(xù)變化的物理量，用以模擬聲音、圖像的變化，故也稱為模擬信號(hào)。因此，波形信源的可以用時(shí)間參數(shù)連續(xù)的隨機(jī)過程進(jìn)行建模和描述。波形信源的模型：波形信源可以用連續(xù)參數(shù)的隨機(jī)過程表示，其中參數(shù)集合或者，隨機(jī)變量表示波形信源在時(shí)刻t所輸出的信號(hào)（例如，一個(gè)振幅或者一個(gè)頻率）。波形信源在任何一段時(shí)間內(nèi)輸出的波形信號(hào)稱為該信源的消息，它是隨機(jī)過程限制在該段時(shí)間上的樣本函數(shù)。形信源的離散化：摸數(shù)轉(zhuǎn)換（A/D transformation）將連續(xù)的模擬量通過取樣和量化兩個(gè)步驟轉(zhuǎn)換為離散的數(shù)字量。例如，對(duì)一幅圖像掃描，將它轉(zhuǎn)換為像素陣列，其中每個(gè)像素由色彩和亮度組成，再對(duì)每個(gè)像素進(jìn)行量化，即從指定的數(shù)值列表中

6、選取最接近像素本身值的整數(shù)值作為像素值的近似表示。這樣原來的圖像就轉(zhuǎn)換為數(shù)字圖像。波形信源產(chǎn)生的波形信號(hào)經(jīng)過離散化后變?yōu)閿?shù)字信號(hào)，從而形成離散信源。離散信源產(chǎn)生的符號(hào)是離散的，例如漢字、字母都是離散符號(hào)，所以漢語和英語是離散信源。數(shù)字線路中傳遞的數(shù)字信號(hào)，所以發(fā)送這些數(shù)字信號(hào)的設(shè)備是離散信源。離散符號(hào)可以編碼為等長的整數(shù)，例如ASCII碼，漢字國家標(biāo)準(zhǔn)碼，等等。因此，我們將離散信源的符號(hào)統(tǒng)一視為整數(shù)。若某離散信源共有n個(gè)符號(hào)，則該離散信源的符號(hào)集記為 離散信源可以用隨機(jī)序列進(jìn)行建模和描述。離散信源的數(shù)學(xué)模型：具有離散時(shí)間參數(shù)和離散狀態(tài)的隨機(jī)序列。 其中隨機(jī)變量Xt表示離散信源在時(shí)刻t所輸出的符

7、號(hào)，即狀態(tài)集中任意整數(shù)。該隨機(jī)序列在一段時(shí)間內(nèi)產(chǎn)生符號(hào)序列就是離散信源的消息。最簡單的離散信源是離散無記憶信源，其定義如下：定義2.1 獨(dú)立同分布序列所表示的離散信源稱為離散無記憶信源，記為DMS。這種信源的符號(hào)序列是獨(dú)立同分布的，即當(dāng)前符號(hào)不影響下一個(gè)符號(hào)的概率分布，并且所有符號(hào)的出現(xiàn)概率在各時(shí)刻都是相同的。當(dāng)我們不考慮信源符號(hào)之間的統(tǒng)計(jì)關(guān)系時(shí)，就可將它粗略地近似為無記憶信源。無損壓縮編碼的目標(biāo)就是將信源改造為均勻分布的無記憶信源。離散無記憶信源可以表征為一個(gè)其符號(hào)集的概率分布：X01n-1 定義2.2 平穩(wěn)隨機(jī)序列所表示的離散信源稱為離散平穩(wěn)信源。平穩(wěn)信源特點(diǎn)是，它在任何時(shí)刻產(chǎn)生同一條消息

8、的概率是相同的。當(dāng)我們研究一個(gè)信源時(shí)，一般假設(shè)它是平穩(wěn)的。平穩(wěn)性大大方便了我們的統(tǒng)計(jì)工作，例如，為了估計(jì)一個(gè)3-漢字組合的概率，我們可以統(tǒng)計(jì)該組合在書本中任何位置上的出現(xiàn)。當(dāng)然現(xiàn)實(shí)的信源可能漸近平穩(wěn)的。即在初始階段可能并不具有平穩(wěn)性，但隨著時(shí)間的推移，變得越來越平穩(wěn)。因此，在統(tǒng)計(jì)時(shí)可以回避不平穩(wěn)的初始階段。例如，統(tǒng)計(jì)一本書中3-漢字組合的出現(xiàn)次數(shù)時(shí)，可以跳過開頭的幾行或者幾段文字。3. 時(shí)齊馬爾科夫鏈離散信源常用的模型是時(shí)齊馬爾科夫鏈，其定義如下。定義3.1 若隨機(jī)序列X在任何時(shí)刻t的t階條件概率等于1階條件概率，即 則稱該隨機(jī)序列滿足馬爾科夫性（Markov property），稱為馬爾科夫

9、序列。 馬爾科夫性也稱為無后效性。這個(gè)性質(zhì)表明：在給定當(dāng)前狀態(tài)的條件下，下一狀態(tài)與以前所有狀態(tài)是相互獨(dú)立的。 定義3.2 狀態(tài)離散的馬爾科夫序列稱為馬爾科夫鏈。 若馬爾科夫鏈的一階條件概率不隨時(shí)間t改變，則稱該馬爾科夫鏈為時(shí)齊的（homogeneous），也稱為時(shí)不變的（time-invariant）。注：與平穩(wěn)性相比較，時(shí)齊性的要求較弱。前者蘊(yùn)含后者，后者并不蘊(yùn)含前者。約定：在以后設(shè)計(jì)馬爾科夫鏈的例題習(xí)題中，若無特別聲明，就默認(rèn)其中馬爾科夫鏈為時(shí)齊的。時(shí)齊馬爾科夫鏈有兩種表征：（1）轉(zhuǎn)移矩陣： 馬爾科夫鏈的所有一階條件概率構(gòu)成的矩陣稱為該馬爾科夫鏈的轉(zhuǎn)移矩陣。轉(zhuǎn)移矩陣是一個(gè)方陣，記錄時(shí)齊馬爾

10、科夫鏈各狀態(tài)之間的轉(zhuǎn)移概率。下列矩陣共有兩行，表明時(shí)齊馬爾科夫鏈共有2個(gè)狀態(tài)，姑且稱為狀態(tài)1和狀態(tài)2。矩陣第1行是狀態(tài)1轉(zhuǎn)移到狀態(tài)2的概率分布，第2行是狀態(tài)2轉(zhuǎn)移到狀態(tài)1的概率分布。 （2）狀態(tài)轉(zhuǎn)移圖：上述矩陣表示的時(shí)齊馬爾科夫鏈也可直觀地表示為如下狀態(tài)轉(zhuǎn)移圖，其中兩個(gè)結(jié)點(diǎn)分別表示兩個(gè)不同狀態(tài)，有向邊稱為狀態(tài)間的轉(zhuǎn)移，有向邊上的標(biāo)記稱為轉(zhuǎn)移概率。 定理3.3令P為時(shí)齊馬爾科夫鏈X的轉(zhuǎn)移矩陣，則t+n時(shí)刻的概率分布為 其中概率分布都表示為行向量。根據(jù)上述定理，我們稱Pn為n-步轉(zhuǎn)移矩陣。命題 若時(shí)齊馬爾科夫鏈?zhǔn)且痪S平穩(wěn)的，則它是任意維平穩(wěn)的。證明：請(qǐng)讀者完成。 證畢一些特殊的初始分布會(huì)使得時(shí)齊馬

11、爾科夫鏈具有平穩(wěn)性，這就是所謂平穩(wěn)分布。定義3.4 令時(shí)齊馬爾科夫鏈（的轉(zhuǎn)移概率矩陣）為P，若存在分布，使得，則稱為平穩(wěn)分布?？梢钥闯?，當(dāng)馬爾科夫鏈的初始分布為平穩(wěn)分布，則該馬爾科夫鏈?zhǔn)瞧椒€(wěn)的。時(shí)齊馬爾科夫鏈的漸近平穩(wěn)性定義3.5（漸近平穩(wěn)性）隨機(jī)序列X稱為漸近平穩(wěn)的，當(dāng)且僅當(dāng)其各維分布存在極限分布，即對(duì)于任何，存在極限 其中稱為n-維極限分布。實(shí)際意義：隨著時(shí)間推移，隨機(jī)序列的統(tǒng)計(jì)特性越來越近似平穩(wěn)序列。命題：時(shí)齊馬爾科夫鏈?zhǔn)菨u近平穩(wěn)的，當(dāng)且僅當(dāng)它存在一維極限分布。命題：極限分布一定是平穩(wěn)分布，而反之未必成立。時(shí)齊馬爾科夫鏈存在極限分布的充分條件：（1）不可約性：若時(shí)齊馬爾科夫鏈的所有狀態(tài)是

12、相互連通的，則稱該馬爾科夫鏈為不可約的（irreducible）。（2）非周期性：從狀態(tài)i出發(fā)再回到i的所有循環(huán)路徑長度的最大公約數(shù)稱為狀態(tài)i的周期。周期等于1的狀態(tài)稱為非周期的（asperiod）。若時(shí)齊馬爾科夫鏈的所有狀態(tài)都是非周期的，則稱該馬爾科夫鏈為非周期的。定理3.6（時(shí)齊馬爾科夫鏈的漸近平穩(wěn)性）若時(shí)齊馬爾科夫鏈P是不可約的和非周期的，則P是漸近平穩(wěn)的，并且其極限分布是唯一的平穩(wěn)分布。 因此，若時(shí)齊馬爾科夫鏈P具有不可約性和非周期性，則其極限分布是下列方程的解： 等價(jià)地， 定理3.7（正則性蘊(yùn)含漸近平穩(wěn)性）若時(shí)齊馬爾科夫鏈P是正則的，即存在正整數(shù)n，使得n-步轉(zhuǎn)移矩陣Pn不含0項(xiàng)，則

13、P是漸近平穩(wěn)的，并且其極限分布是唯一的平穩(wěn)分布。注：n-步轉(zhuǎn)移矩陣Pn不含0項(xiàng)的含義是，從任何狀態(tài)出發(fā)經(jīng)過n-步轉(zhuǎn)移都可達(dá)到其它任何狀態(tài)。練習(xí)判斷下列馬爾科夫鏈?zhǔn)欠翊嬖跇O限分布。若存在試求出該極限分布。 練習(xí)設(shè)任意相繼的兩天中，雨天轉(zhuǎn)晴天的概率為1/3，晴天轉(zhuǎn)雨天的概率為1/2，任一天晴或者雨是互為逆事件。以0和1分別表示晴天和雨天這兩種狀態(tài)，Xn表示第n天的狀態(tài)（0或1）。試寫出馬氏鏈的轉(zhuǎn)移矩陣。又若已知5月1日為晴天，問5月3日為晴天，5月4日為雨天的概率各等于多少？4. 馬爾科夫信源 定義4.1 若隨機(jī)序列X在任何時(shí)刻t的t階條件概率等于m階條件概率（其中mt），即 則稱該隨機(jī)序列具有m

14、-階馬爾科夫性，并稱該序列為m階馬爾科夫序列。m階馬爾科夫序列所表示的離散信源稱為m階馬爾科夫信源。m階馬爾科夫性表明隨機(jī)序列具有有限的記憶性，我們稱其記憶長度為m+1.根據(jù)定義，馬爾科夫鏈?zhǔn)?階馬爾科夫序列，其記憶長度等于2。 漢語、英語等自然語言都具有這種有限記憶性。在漢語文章中，一個(gè)漢字僅與前幾個(gè)漢字的關(guān)系比較密切，而與更前面的漢字的關(guān)系較弱，可以忽略不計(jì)。根據(jù)實(shí)際需要，我們可以構(gòu)造漢語的1-階馬爾科夫模型、2-階馬爾科夫模型，等等。模型的階數(shù)越大，則該模型的條件概率矩陣越龐大，從而構(gòu)造和應(yīng)用該條件概率矩陣所需的統(tǒng)計(jì)和計(jì)算工作量越大。最常用的是3-單詞模型。5. 構(gòu)造英語的馬爾科夫模型在

15、研究實(shí)際信源時(shí)，可根據(jù)實(shí)際需要，選擇合適的信源模型。我們介紹英語信源模型的構(gòu)造方法。這個(gè)方法是香農(nóng)在1948年的論文A mathematical theory of communication中給出的。它通過統(tǒng)計(jì)一本書中英文字符間的條件概率而構(gòu)造英文的幾種馬爾科夫模型。（本教材此處內(nèi)容參考自Cover與Thomas的教材信息論基礎(chǔ)第2版第96頁。）首先，確定英文字母表：為簡化統(tǒng)計(jì)和計(jì)算的工作量，假設(shè)英文字母表僅包括27個(gè)符號(hào)，即26個(gè)字母和常見的空格符號(hào)，忽略標(biāo)點(diǎn)和大小寫。討論：英語符號(hào)簡化為27個(gè)符號(hào)對(duì)于估計(jì)其熵率的影響大嗎？其次，任意選取一本足夠厚重的英文著作。按下列方法統(tǒng)計(jì)條件概率。無記

16、憶模型：這個(gè)模型假設(shè)英文是無記憶信源。更加該假設(shè)，做如下統(tǒng)計(jì)工作。選擇一本英文書，統(tǒng)計(jì)出其中各符號(hào)出現(xiàn)頻率p(x)，構(gòu)成英文字符的一維分布列，其形式如下：Xabz空格一階馬爾科夫模型：從所選的英文書中，統(tǒng)計(jì)出英語符號(hào)的一階條件概率，構(gòu)成一個(gè)轉(zhuǎn)移矩陣，這個(gè)轉(zhuǎn)移矩陣就是英文的一階馬爾科夫模型。統(tǒng)計(jì)方法如下。第1步，隨機(jī)地打開書本中的某頁，并隨機(jī)地選定一個(gè)符號(hào)，作為該序列的第1個(gè)符號(hào)。第2步，隨機(jī)地打開某頁，找到當(dāng)前選定的符號(hào)Xi，將緊隨其后的符號(hào)選定為下一個(gè)符號(hào)。第3步，重復(fù)第2步，直到所構(gòu)造的序列足夠長時(shí)為止。這種隨機(jī)跳躍式的統(tǒng)計(jì)方法可以構(gòu)造出具有一階馬爾科夫性的符號(hào)序列。只要所構(gòu)造的符號(hào)序列足

17、夠長，則足以代表英語字符序列的一階馬爾科夫性。第4步 從所構(gòu)造的符號(hào)序列中統(tǒng)計(jì)出相鄰符號(hào)間的條件概率，構(gòu)成一階馬爾科夫模型的轉(zhuǎn)移矩陣。m階馬爾科夫模型：類似地，從最初隨機(jī)選定的連續(xù)m個(gè)符號(hào)開始，隨機(jī)跳躍若干行符號(hào)后，找該符號(hào)組的第1次出現(xiàn)，從而將該符號(hào)組之后的第1個(gè)符號(hào)選定下一個(gè)符號(hào)。依次類推，構(gòu)造出一個(gè)足夠長的符號(hào)序列。該序列可以反映英語的m階馬爾科夫性。從該序列中統(tǒng)計(jì)出所有m分組與緊跟其后的下一個(gè)符號(hào)之間的條件概率。所有的這些概率構(gòu)成一個(gè)矩陣，這就是英語的m階馬爾科夫模型。上述構(gòu)造的是以英文字符為符號(hào)的馬爾科夫模型，稱為馬爾科夫字符模型。香農(nóng)在1948年的文章中還介紹了以單詞為符號(hào)的馬爾科

18、夫模型，稱為馬爾科夫單詞模型，其構(gòu)造方法與上述介紹的方法類似。英語的馬爾科夫模型中最常用的是三單詞模型，即2階馬爾科夫單詞模型，在語音識(shí)別系統(tǒng)中起到關(guān)鍵的作用，獲得了驚人的效果。6. 隱馬爾可夫鏈 對(duì)于m-階馬爾科夫信源，我們將信源符號(hào)的所有m-分組視為新的信源符號(hào)，從而可將該信源轉(zhuǎn)化為1-階馬爾科夫信源，即馬爾科夫鏈。令為m-階馬爾科夫序列。令，其中 易知Y的記憶長度為1，即所以Y是馬爾科夫鏈，稱為X的隱馬爾科夫鏈。因此，通過符號(hào)分組，可以將m-階馬爾科夫信源轉(zhuǎn)化為形式比較簡單的馬爾科夫鏈。在隨機(jī)過程理論中，對(duì)于馬爾科夫鏈的研究是比較成熟的，許多研究結(jié)果可以應(yīng)用到信源研究上。意義：（1） m-階馬爾科夫信源也可以轉(zhuǎn)化為馬爾科夫信源，便于分析和處理。（2）任何m-階馬爾科夫信源都可以視為馬爾科夫信源。前一概念完全可以被后一概念所取代。例6.1（傅祖蕓，趙建中信息論與編碼第54頁例2.11）設(shè)X是二元二階馬爾科夫序列，其條件概率矩陣P(X3|X1X2)如下： 根據(jù)該矩陣可以確定X的隱馬爾科夫模