《信息論與編碼》全套教學(xué)課件

信息論與編碼第1章緒論第2章信源及其熵第3章信道及其信道容量第4章率失真函數(shù)第5章信源編碼第6章信道編碼第7章保密編碼全套可編輯PPT課件信息論與編碼第1章緒論第1章緒論1.1信息的概念1.1.1信息科技促使人們對(duì)信息概念進(jìn)行更深刻的剖析與理解如今，與ICT直接或者間接關(guān)聯(lián)的技術(shù)、技術(shù)產(chǎn)品、技術(shù)服務(wù)及技術(shù)規(guī)范，已經(jīng)全面滲透到了人們的工作與生活。對(duì)任何ICT技術(shù)的深入學(xué)習(xí)、研發(fā)與應(yīng)用，都難以回避知曉或理解大量ICT名詞所蘊(yùn)含的學(xué)術(shù)與技術(shù)原理。各式各樣的ICT技術(shù)概念與產(chǎn)品服務(wù)，艱深玄奧的信息科學(xué)原理與方法，在帶給人們獲得科技福祉的同時(shí)，也帶給人們認(rèn)識(shí)信息科技及信息概念的多種困擾，這些困擾的根源常常都是沒有明確解釋“信息是什么”。因此，有必要通過交流和研討去逐漸形成關(guān)于信息基本概念的共識(shí)認(rèn)知。第1章緒論1.1信息的概念1.1.2信息是特定場(chǎng)景中的“信息”信息的本原意蘊(yùn)需要結(jié)合信息處理場(chǎng)景的分析才更容易獲得充分的理解。信息由信息的發(fā)生源（稱其為信源）發(fā)出，經(jīng)由信息處理過程（稱其為信道）傳遞或推送給信息處理的承載方或者接收方（稱其為信宿）第一章緒論1.1信息的概念1.1.3信息的基本屬性信息處理的基本特征與屬性可以歸納為“老四性”與“新三性”。信息處理的“老四性”界定了信息論研究的基礎(chǔ)范疇，（1）可行性（2）有效性（3）可靠性（4）安全性信息處理的“新三性”是在現(xiàn)代信息科學(xué)背景下對(duì)信息本原屬性的更深層次探索。（1）本原性（2）時(shí)空性（3）效用性或者價(jià)值性或者賽博性第1章緒論1.1信息的概念1.1.4信息的香農(nóng)定義與維納定義香農(nóng)的信息定義：信息是信宿關(guān)于信源的不確定性。維納的信息定義：信息是對(duì)信宿有效用的關(guān)于信源的不確定性。1.2信息論的研究?jī)?nèi)容1.2.1信息度量、信息熵與消息對(duì)于離散信源對(duì)于連續(xù)信源第1章緒論1.2信息論的研究?jī)?nèi)容1.2.2信息表征與數(shù)據(jù)壓縮

信息表征的理論基礎(chǔ)由香農(nóng)信源編碼定理（又稱為數(shù)據(jù)壓縮定理或香農(nóng)第一定理）給出，具體地，香農(nóng)信源編碼定理又細(xì)分為無失真信源編碼定理和限失真信源編碼定理。

對(duì)于無失真信源編碼定理的簡(jiǎn)單解釋是：壓縮編碼序列長(zhǎng)度的最小值等于壓縮前序列長(zhǎng)度乘以信源熵。

限失真信源編碼定理指出了給定失真度限制條件下的編碼方法的存在性第1章緒論1.2信息論的研究?jī)?nèi)容1.2.3信息傳輸、信道容量、調(diào)制與編碼信道傳輸特征由信道的熵特征確定；條件熵完全界定了信道上消息的傳輸特征信道傳輸?shù)淖畲笮畔⒘繛樾诺廊萘?/p>

。BSC和AWGN信道上的信息傳輸原理是其他信道上信息傳輸原理的基礎(chǔ)；第1章緒論1.2信息論的研究?jī)?nèi)容1.2.4信息安全、加密與認(rèn)證應(yīng)對(duì)兩類信息安全威脅，通常最可信的措施是加密（通過消息數(shù)據(jù)加密實(shí)現(xiàn)信息隱私保護(hù)）和簽名（通過消息數(shù)據(jù)簽名實(shí)現(xiàn)信息認(rèn)證保護(hù)）。應(yīng)對(duì)信息認(rèn)證安全威脅，即實(shí)現(xiàn)信息真實(shí)性與完整性保護(hù)的途徑主要有數(shù)字簽名、消息認(rèn)證碼、區(qū)塊鏈等。第1章緒論第1章1.3從“香農(nóng)貢獻(xiàn)”洞悉信息科技1.3.1香農(nóng)的信息科技創(chuàng)新貢獻(xiàn)1936年碩士學(xué)位論文《繼電器和開關(guān)電路的符號(hào)分析》；1940年香農(nóng)的博士學(xué)位論文《理論遺傳學(xué)的代數(shù)學(xué)》；1948年劃時(shí)代成果《通信的數(shù)學(xué)理論》；1.3.2香農(nóng)培養(yǎng)的后起之秀與留存后世的至理名言RobertG.Gallager于1963年在其博士論文中提出的“LDPC碼”；香農(nóng)的一句至理名言是：“Ijustwonderedhowthingswereputtogether（我特感奇妙的是事物因何如此匯聚一體）”1.4從香農(nóng)獎(jiǎng)看信息論的發(fā)展歷程第1章緒論THEEND!信息論與編碼第2章信源及其熵2.1信源與信息度量的基本概念第2章信源及其熵2.1

信源與信息度量的基本概念信源是信息的產(chǎn)生源。信息是抽象的，但它可以通過消息來進(jìn)行表達(dá)和傳遞。按照信源發(fā)出的消息在時(shí)間和幅度上的分布情況分類，可將信源分成離散信源、連續(xù)信源和半離散半連續(xù)信源。離散信源是指發(fā)出時(shí)間和幅度都是離散分布的離散消息的信源，如發(fā)出文字、數(shù)字等離散消息的信源。連續(xù)信源是指發(fā)出在時(shí)間和幅度上都是連續(xù)分布的連續(xù)消息（模擬消息）的信源，如發(fā)出語音、圖像等連續(xù)消息的信源，連續(xù)信源也稱為波形信源。2.1

信源與信息度量的基本概念半離散半連續(xù)信源是指發(fā)出的消息在時(shí)間和幅度上可以一個(gè)是離散的、另一個(gè)是連續(xù)的信源。例如，模擬信號(hào)在時(shí)間上抽樣以后得到的信號(hào)在時(shí)間上是離散的，在幅度取值上是連續(xù)的。離散信源可以進(jìn)一步進(jìn)行如下分類：（1）離散無記憶信源。它發(fā)出的各符號(hào)是相互獨(dú)立的，也就是信源發(fā)出的符號(hào)序列中的各符號(hào)之間沒有統(tǒng)計(jì)關(guān)聯(lián)性，各符號(hào)的出現(xiàn)概率是它自身的先驗(yàn)概率。發(fā)出單個(gè)符號(hào)的無記憶信源是指每次只發(fā)出一個(gè)符號(hào)代表一個(gè)消息的離散無記憶信源。

發(fā)出符號(hào)序列的無記憶信源是指每次發(fā)出一組含兩個(gè)以上符號(hào)的符號(hào)序列代表一個(gè)消息的離散無記憶信源。2.1

信源與信息度量的基本概念（2）離散有記憶信源。它發(fā)出的各個(gè)符號(hào)的概率是有關(guān)聯(lián)的。這種概率關(guān)聯(lián)性可用兩種方式表示：第一種方式是用信源發(fā)出的一個(gè)符號(hào)序列的整體概率（聯(lián)合概率）反映有記憶信源的特征，即發(fā)出符號(hào)序列的有記憶信源；

第二種方式是用信源發(fā)出的符號(hào)序列內(nèi)各符號(hào)之間的條件概率來反映記憶特征，即發(fā)出符號(hào)序列的馬爾可夫信源。2.2自信息量與熵第2章信源及其熵2.2

自信息量與熵

2.2.1

自信息量信息量定義為 I(信息量)=不確定程度的減少量也就是說，收信者收到一個(gè)消息后，所獲得的信息量等于收到消息前后不確定程度的減少量。1．自信息量定義2.1

任意隨機(jī)事件的自信息量定義為該事件發(fā)生概率的對(duì)數(shù)的負(fù)值。

隨機(jī)事件的不確定性在數(shù)量上等于其自信息量。因此小概率事件所包含的不確定性高，其自信息量大；反之，大概率事件所包含的不確定性低，其自信息量小。2．聯(lián)合自信息量

且聯(lián)合概率是完備的，即

3．條件自信息量

2.2.2

信息熵1．信息熵

2．條件熵

3．共熵（聯(lián)合熵）

共熵與熵及條件熵之間存在下列關(guān)系：

4．相對(duì)熵

相對(duì)熵，也稱為KL散度、KL距離。在信息系統(tǒng)中稱為相對(duì)熵，在連續(xù)時(shí)間序列中稱為隨機(jī)性，在統(tǒng)計(jì)模型推斷中稱為信息增益，也稱為信息散度。相對(duì)熵是兩個(gè)概率分布和差別的非對(duì)稱性的度量。

5．交叉熵

交叉熵性質(zhì)：2.2.3

熵的基本性質(zhì)

性質(zhì)4熵函數(shù)具有擴(kuò)展性，即

其中性質(zhì)6熵函數(shù)具有確定性，即性質(zhì)7熵函數(shù)具有凸性，即是的上凸函數(shù)。

性質(zhì)8條件熵小于無條件熵，即

2.3互信息量與平均互信息量第2章信源及其熵2.3

互信息量與平均互信息量1.互信息量的定義2.3.1互信息量

再由自信息量和條件自信息量的定義公式，不難推出互信息量的概率計(jì)算式：

2.互信息量的性質(zhì)性質(zhì)1互信息量具有互易性，即推導(dǎo)過程如下：性質(zhì)2獨(dú)立變量的互信息量為0。

事件之間存在互信息量，與事件之間的統(tǒng)計(jì)相關(guān)。如果和統(tǒng)計(jì)獨(dú)立，不難證明互信息量為0。性質(zhì)3互信息量可正可負(fù)性質(zhì)4互信息量不可能大于符號(hào)的實(shí)在信息，即

互信息量的物理意義是：一個(gè)接收者獲得的關(guān)于某個(gè)符號(hào)的信息量不可能大于該符號(hào)本身所攜帶的實(shí)在信息量。3.條件互信息量

可寫成推導(dǎo)過程如下：

1.平均互信息量的定義2.3.2平均互信息量

2.平均互信息量的性質(zhì)性質(zhì)1平均互信息量具有非負(fù)性，即性質(zhì)2平均互信息量具有對(duì)稱性，即

性質(zhì)3平均互信息量具有極值性，即

其中，性質(zhì)5平均互信息量和各類熵的關(guān)系如下平均互信息量和熵、條件熵的關(guān)系為

平均互信息量和熵、共熵的關(guān)系為

圖.平均互信息量與各種熵的關(guān)系為了更便于理解，我們?cè)侔阉鼈兊年P(guān)系列于表中性質(zhì)6三維聯(lián)合符號(hào)集合上的平均互信息量為根據(jù)平均互信息量的對(duì)稱性，可得3.平均互信息量的物理意義

對(duì)于無擾離散信道，因?yàn)樾诺郎蠜]有噪聲，所以信道不損失信息量，疑義度為零，噪聲熵也為零。于是有

2.4離散信源的熵第2章信源及其熵2.4

離散信源的熵2.4.1單符號(hào)離散信源的熵

當(dāng)對(duì)數(shù)底取2時(shí)，信源的熵的單位為比特/符號(hào)。2.4.2多符號(hào)離散信源的熵

且有2.4.3馬爾可夫信源的熵

馬爾可夫鏈可以用香農(nóng)線圖表示。

2.4.4離散信源的時(shí)間熵1．發(fā)出單個(gè)符號(hào)消息的離散無記憶信源的時(shí)間熵已知離散無記憶信源的各個(gè)符號(hào)的概率分布為

此時(shí)，該信源的時(shí)間熵又可表示為

2.5連續(xù)信源的熵第2章信源及其熵2.5

連續(xù)信源的熵2.5.1單符號(hào)連續(xù)信源的熵

連續(xù)隨機(jī)變量可以通過離散化，用離散隨機(jī)變量來逼近，也就是說，連續(xù)隨機(jī)變量可以認(rèn)為是離散隨機(jī)變量的極限情況，我們從這個(gè)角度來討論連續(xù)隨機(jī)變量的熵。

在定義連續(xù)信源的熵時(shí)把第二項(xiàng)（絕對(duì)熵）舍去，定義的連續(xù)信源的熵為這樣定義的熵，稱為連續(xù)隨機(jī)變量的微分熵。計(jì)算幾種特殊連續(xù)信源的熵1.均勻分布的連續(xù)信源的熵

則一維連續(xù)信源的熵為

由此可求得N維連續(xù)信源的微分熵為基本高斯信源是指信源輸出的一維隨機(jī)變量的概率密度函數(shù)是正態(tài)分布的，即

2.高斯分布的連續(xù)信源的熵這個(gè)連續(xù)信源的熵為

則稱X代表的單變量連續(xù)信源為指數(shù)分布的連續(xù)信源。其中常數(shù)m是隨機(jī)變量X的數(shù)學(xué)期望，即3.指數(shù)分布的連續(xù)信源的熵指數(shù)分布的連續(xù)信源的熵為其中有其中2.5.2連續(xù)信源的熵的性質(zhì)

由Jensen不等式得出，故有當(dāng)且僅當(dāng)時(shí)等號(hào)才成立。說明了在信源輸出信號(hào)的幅度受限條件下（或峰值功率受限條件下），任何概率密度函數(shù)的熵必定小于或等于均勻分布的概率密度函數(shù)的熵。

所以根據(jù)Jensen不等式得

也就是說，連續(xù)信源的輸出信號(hào)平均功率受限時(shí)，只有當(dāng)信源服從高斯分布時(shí)，才會(huì)有最大的熵值。定理2.3（均值受限條件下的最大熵定理）對(duì)于輸出非負(fù)消息且均值受限的一維連續(xù)信源，當(dāng)輸出信號(hào)的概率密度函數(shù)服從指數(shù)分布時(shí)，其微分熵達(dá)到最大值。

首先有所以有因而有

2.5.3多符號(hào)連續(xù)信源的熵

各類微分熵之間存在與離散熵相類似的關(guān)系，如恒等關(guān)系：不等關(guān)系：

證明式同理可得

平均互信息量概念本身就具有相對(duì)意義，求平均互信息量時(shí)，實(shí)際連續(xù)隨機(jī)變量微分熵中的無窮大項(xiàng)相互抵消了，只剩下有限值相減。由此可推出平均互信息量與微分熵之間的關(guān)系，即基本性質(zhì)

性質(zhì)1非負(fù)性，即性質(zhì)2對(duì)稱性，即

2.5.4熵功率在信號(hào)平均功率受限時(shí)，高斯隨機(jī)變量的熵最大。假定高斯隨機(jī)變量的平均功率為，那么此時(shí)高斯隨機(jī)變量的熵為

因此，熵功率給出了隨機(jī)變量功率的一個(gè)上界。值得注意的是，當(dāng)信源為高斯隨機(jī)變量時(shí)，其熵功率就是其平均功率。2.6信息論不等式及其應(yīng)用第2章信源及其熵2.6信息論不等式及其應(yīng)用

2.6.1對(duì)數(shù)和不等式及其應(yīng)用

這就是對(duì)數(shù)和不等式。

2.6.2數(shù)據(jù)處理不等式

證明：由鏈?zhǔn)椒▌t，將平均互信息量以兩種不同方式展開：

2.6.3數(shù)據(jù)處理定理圖

兩級(jí)處理器示意圖定理2.7（數(shù)據(jù)處理定理）當(dāng)消息通過多級(jí)處理器時(shí)，隨著處理器數(shù)量的增多，輸入消息與輸出消息之間的平均互信息量趨于變小。對(duì)于圖所示的兩級(jí)級(jí)聯(lián)處理器的情況，有證明：由平均互信息量基本性質(zhì)，得

得

2.6.4費(fèi)諾不等式

上述不等式可以減弱為或

證明：定義一個(gè)誤差隨機(jī)變量利用熵的鏈?zhǔn)椒▌t將以兩種不同方式展開，有

第2章信源及其熵THEEND!信息論與編碼第3章信道及其信道容量第3章信道及其信道容量3.1信道及其信道容量的基本概念3.1.1信道的數(shù)學(xué)模型及其分類單符號(hào)離散信道的數(shù)學(xué)模型信道的統(tǒng)計(jì)特性由條件概率組成的信道轉(zhuǎn)移矩陣描述根據(jù)輸入符號(hào)和輸出符號(hào)的特點(diǎn)分類離散信道|連續(xù)信道|半離散半連續(xù)信道|波形信道第3章信道及其信道容量3.1信道及其信道容量的基本概念3.1.2信道容量的定義信道容量是描述信道特性的參量，只與信道的統(tǒng)計(jì)特性有關(guān)。第3章信道及其信道容量3.2單符號(hào)離散信道及其信道容量3.2.1特殊單符號(hào)離散信道及其信道容量無噪無損信道及其信道容量無噪有損信道及其信道容量有噪無損信道及其信道容量第3章信道及其信道容量3.2單符號(hào)離散信道及其信道容量3.2.2對(duì)稱離散信道及其信道容量強(qiáng)對(duì)稱離散信道及其信道容量對(duì)稱離散信道及其信道容量行可排列列可排列二元對(duì)稱信道及其信道容量其中信道轉(zhuǎn)移概率是p第3章信道及其信道容量3.2單符號(hào)離散信道及其信道容量3.2.3準(zhǔn)對(duì)稱離散信道及其信道容量單符號(hào)離散信道轉(zhuǎn)移矩陣是行可排列、列不可排列的準(zhǔn)對(duì)稱信道的信道容量的輸入分布是等概率分布，準(zhǔn)對(duì)稱信道的信道容量的表達(dá)式為二元?jiǎng)h除信道（BEC）及其信道容量第3章信道及其信道容量3.2單符號(hào)離散信道及其信道容量3.2.4一般離散無記憶信道及其信道容量

對(duì)于一般離散無記憶信道而言，求其信道容量，就是在信道固定的條件下，對(duì)所有可能的輸入概率分布，求平均互信息量的極大值第3章信道及其信道容量3.3多符號(hào)離散信道及其信道容量3.3.1多符號(hào)離散信道的數(shù)學(xué)模型多符號(hào)離散信道的數(shù)學(xué)模型可以用序列（向量）條件概率分布描述為第3章信道及其信道容量3.3多符號(hào)離散信道及其信道容量3.3.2多符號(hào)離散信道的信道容量多符號(hào)離散信道的信道容量的計(jì)算比較復(fù)雜，特別是有記憶的離散序列信道的信道容量的計(jì)算，至今沒有有效的求解方法。第3章信道及其信道容量3.3多符號(hào)離散信道及其信道容量3.3.3離散N次擴(kuò)展信道的信道容量第3章信道及其信道容量3.3多符號(hào)離散信道及其信道容量3.3.4獨(dú)立并聯(lián)信道的信道容量一般情況下的獨(dú)立并聯(lián)信道的信道容量滿足以下關(guān)系若輸入信道的N個(gè)隨機(jī)變量相互獨(dú)立，且達(dá)到各自信道容量的最佳輸入概率分布時(shí)，

達(dá)到最大值第3章信道及其信道容量3.3多符號(hào)離散信道及其信道容量3.3.5串聯(lián)信道的信道容量串聯(lián)的無源數(shù)據(jù)處理信道越多，其信道容量（最大信息率）可能越小，當(dāng)串聯(lián)的信道數(shù)無窮大時(shí)，信道容量就可能趨近于零。第3章信道及其信道容量3.4連續(xù)信道及其信道容量3.4.1單符號(hào)連續(xù)信道及其信道容量單符號(hào)連續(xù)信道的信道容量

為信源取某一概率密度函數(shù)時(shí)，平均互信息量的最大值高斯加性信道的信道容量為第3章信道及其信道容量3.4連續(xù)信道及其信道容量3.4.2多符號(hào)無記憶高斯加性信道及其信道容量多符號(hào)無記憶高斯加性信道的信道容量，該信道的取值是連續(xù)的，但是在時(shí)間上是離散的第3章信道及其信道容量3.4連續(xù)信道及其信道容量3.4.3限帶高斯白噪聲加性波形信道機(jī)器信道容量高斯白噪聲加性波形信道是經(jīng)常假設(shè)的一種時(shí)間和幅度上都連續(xù)的信道第3章信道及其信道容量3.5MIMO信道和多址接入信道及其信道容量3.5.1MIMO信道及其信道容量MIMO系統(tǒng)的信號(hào)模型可以表示為確定性MIMO信道的信道容量可以表示為隨機(jī)MIMO信道的平均信道容量可以表示為第3章信道及其信道容量3.5MIMO信道和多址接入信道及其信道容量3.5.2多址接入信道及其信道容量多址接入信道模型這些限制條件在N維空間中規(guī)定了一個(gè)截去角的多面體，這個(gè)多面體內(nèi)就是信道允許的多用戶的信息率，多面體的上界就是多址接入信道的信道容量第3章信道及其信道容量THEEND!信息論與編碼第4章率失真函數(shù)第4章率失真函數(shù)4.1率失真函數(shù)的基本概念4.1.1實(shí)驗(yàn)信道離散信道：數(shù)據(jù)處理信道的正向和反向轉(zhuǎn)移矩陣表示為所有失真函數(shù)均可以和保真度準(zhǔn)則表示為試驗(yàn)信道和反向?qū)嶒?yàn)信道的信道轉(zhuǎn)移矩陣為第4章率失真函數(shù)4.1率失真函數(shù)的基本概念4.1.1實(shí)驗(yàn)信道連續(xù)信源失真函數(shù)平均失真度保真度準(zhǔn)則試驗(yàn)信道第4章率失真函數(shù)4.1率失真函數(shù)的基本概念4.1.2率失真函數(shù)的定義最小平均互信息量為率失真函數(shù)第4章率失真函數(shù)4.1率失真函數(shù)的基本概念4.1.3率失真函數(shù)的性質(zhì)離散信源的最小允許失真度及率失真函數(shù)為連續(xù)信源的最小允許失真度及率失真函數(shù)為離散信源的最大允許失真度及率失真函數(shù)為連續(xù)信源的最大允許失真度及率失真函數(shù)為單調(diào)遞減第4章率失真函數(shù)4.2離散信源的率失真函數(shù)4.2.1離散信源率失真函數(shù)的一般形式由于試驗(yàn)信道的損失熵對(duì)反向轉(zhuǎn)移概率嚴(yán)格上凸，其極值為最大值。為求極值，可以構(gòu)造拉格朗日函數(shù)：求出使試驗(yàn)信道的損失熵達(dá)到極值的滿足保真度準(zhǔn)則的反向轉(zhuǎn)移概率，即試驗(yàn)信道的反向轉(zhuǎn)移概率，進(jìn)而求出試驗(yàn)信道的最大損失熵。第4章率失真函數(shù)4.2離散信源的率失真函數(shù)4.2.2二元信源和等概信源的率失真函數(shù)二元信源二元信源的率失真函數(shù)為達(dá)到

的試驗(yàn)信道的反向和正向信道轉(zhuǎn)移矩陣為第4章率失真函數(shù)4.2離散信源的率失真函數(shù)4.2.2二元信源和等概信源的率失真函數(shù)等概信源等概率信源的率失真函數(shù)為達(dá)到

的試驗(yàn)信道的反向和正向信道轉(zhuǎn)移矩陣為第4章率失真函數(shù)4.3連續(xù)信源的率失真函數(shù)4.3.1連續(xù)信源率失真函數(shù)的一般形式信源的率失真函數(shù)為由于試驗(yàn)信道的損失差熵對(duì)反向轉(zhuǎn)移概率密度函數(shù)嚴(yán)格上凸，其極值為最大值。為求極值，可以構(gòu)造拉格朗日函數(shù)：求出使試驗(yàn)信道的損失差熵達(dá)到極值的滿足保真度準(zhǔn)則的反向轉(zhuǎn)移概率密度函數(shù)，即試驗(yàn)信道的反向轉(zhuǎn)移概率密度函數(shù)，進(jìn)而求出試驗(yàn)信道的最大損失差熵。并令第4章率失真函數(shù)4.3連續(xù)信源的率失真函數(shù)4.3.2高斯信源的率失真函數(shù)高斯信源的率失真函數(shù)為達(dá)到R(D)的試驗(yàn)信道的反向轉(zhuǎn)移概率密度函數(shù)為第4章率失真函數(shù)THEEND!信息論與編碼第5章信源編碼第5章信源編碼5.1異前置碼與無失真信源編碼定理5.1.1異前置碼唯一可譯碼又分為非即時(shí)碼和即時(shí)碼，即時(shí)碼又稱為非延長(zhǎng)碼或前綴碼，任意一個(gè)碼字都不是其他碼字的前綴部分唯一可譯碼存在的充分必要條件，即各碼字的長(zhǎng)度

，應(yīng)符合克拉夫特不等式（Kraft’sinequality），即第5章信源編碼5.1異前置碼與無失真信源編碼定理5.1.2無失真信源編碼定理對(duì)于熵為H(X)的無記憶信源X的N次擴(kuò)展信源（熵

NH(X)），必然存在一種無失真的m進(jìn)制編碼方法，當(dāng)N足夠大時(shí)，平均碼長(zhǎng)滿足不等式如果

m=2，則得到平均碼長(zhǎng)

滿足下列不等式第5章信源編碼5.2經(jīng)典無失真信源編碼5.2.1霍夫曼碼霍夫曼碼是按照小概率消息編長(zhǎng)碼、大概率消息編短碼的思想來構(gòu)造異前置碼的一種信源編碼方法。5.2.2費(fèi)諾碼費(fèi)諾碼是按照碼元的概率盡可能相等的思想來構(gòu)造異前置碼的一種信源編碼方法。5.2.3香農(nóng)-費(fèi)諾-埃利斯碼霍夫曼碼和費(fèi)諾碼算法都要求信源輸出符號(hào)按概率大小排序，香農(nóng)-費(fèi)諾-埃利斯碼（Shannon-Fano-Elias碼，S-F-E碼）不需這種排序。第5章信源編碼5.2經(jīng)典無失真信源編碼5.2.4算術(shù)碼由無失真信源編碼定理可知，僅對(duì)信源輸出的單個(gè)符號(hào)進(jìn)行編碼，其效率是不高的，只有對(duì)信源輸出的符號(hào)序列進(jìn)行編碼，并且當(dāng)序列長(zhǎng)度充分長(zhǎng)時(shí)，編碼效率才達(dá)到香農(nóng)定理的極限。算術(shù)碼是性能最好的一種信源序貫編碼方法算術(shù)碼的核心思想是將信源序列按概率映射在單位區(qū)間

中的一段子區(qū)間，使得概率高的序列被分配的子區(qū)間長(zhǎng)度長(zhǎng)，概率低的序列被分配的子區(qū)間長(zhǎng)度短，在此基礎(chǔ)上保證各個(gè)序列對(duì)應(yīng)的子區(qū)間不重疊，那么就可以通過采樣子區(qū)間中的某一個(gè)二進(jìn)制小數(shù)對(duì)信源序列進(jìn)行唯一可譯的編碼。第5章信源編碼

第5章信源編碼5.4限失真信源編碼方法5.4.1量化編碼脈沖編碼調(diào)制（PulseCodeModulation，PCM）是研究最早、使用最廣的一種最佳標(biāo)量量化編碼。PCM的編碼原理如圖所示。第5章信源編碼5.4限失真信源編碼方法5.4.2相關(guān)信源編碼采樣后的信號(hào)序列在時(shí)間上彼此獨(dú)立，對(duì)各個(gè)采樣時(shí)刻的信號(hào)值逐個(gè)進(jìn)行量化，可以做到最佳標(biāo)量量化。但如果是有記憶信源，采樣后的信號(hào)序列就存在時(shí)間相關(guān)性。為提高編碼效率，對(duì)于時(shí)間相關(guān)的信號(hào)序列，通常用兩類方法進(jìn)行編碼：一類方法是利用信號(hào)序列的時(shí)間相關(guān)性，通過預(yù)測(cè)減少信息冗余后再進(jìn)行編碼，這類方法稱為預(yù)測(cè)編碼；另一類方法是引入某種變換，將信號(hào)序列變換為另一個(gè)時(shí)間上彼此獨(dú)立或相關(guān)程度較低的序列，再對(duì)這個(gè)新序列進(jìn)行編碼，這類方法稱為變換編碼。第5章信源編碼5.4限失真信源編碼方法5.4.3JPEG圖像編碼JPEG（JointPhotographExpertGroup）是第一個(gè)靜止圖像編碼國際標(biāo)準(zhǔn)5.4.4H.264/AVC視頻編碼H.264/AVC視頻編碼是由ITU-T視頻編碼專家組（VCEG）和ISO/IEC動(dòng)態(tài)圖像專家組（MPEG）聯(lián)合組成的聯(lián)合視頻組（JointVideoTeam，JVT）提出的高效數(shù)字視頻編解碼器標(biāo)準(zhǔn)。第5章信源編碼THEEND!信息論與編碼第6章信道編碼第6章信道編碼6.1信道編碼與差錯(cuò)控制6.1.1信道編碼的基本概念信道編碼是指針對(duì)有噪信道傳輸設(shè)計(jì)的一個(gè)或一組變換或映射規(guī)則，發(fā)送端的信道編碼器通過增加冗余符號(hào)將被傳輸?shù)南⑿蛄凶儞Q或映射成編碼符號(hào)序列或碼字，接收端的信道譯碼器基于信道編碼的映射規(guī)則和信道特性發(fā)現(xiàn)傳輸中的錯(cuò)誤，甚至可以自行糾正錯(cuò)誤。碼率漢明重量與漢明距離最小漢明距離（最小碼距）第6章信道編碼6.1信道編碼與差錯(cuò)控制6.1.2最大似然譯碼準(zhǔn)則最大后驗(yàn)概率譯碼準(zhǔn)則就可表示為：最大似然譯碼準(zhǔn)則在輸入符號(hào)等概率時(shí)，最大后驗(yàn)概率譯碼準(zhǔn)則和最大似然譯碼準(zhǔn)則是等價(jià)的第6章信道編碼6.1信道編碼與差錯(cuò)控制6.1.3譯碼模式與糾檢錯(cuò)能力譯碼模式或譯碼器工作模式：檢錯(cuò)模式、糾錯(cuò)模式、混合糾檢錯(cuò)模式檢糾錯(cuò)數(shù)定理：檢錯(cuò)模式時(shí)在糾錯(cuò)模式時(shí)在混合糾檢錯(cuò)模式時(shí)第6章信道編碼6.1信道編碼與差錯(cuò)控制6.1.4差錯(cuò)控制方式除了以上三種基本方式，還有一種方式是混合糾錯(cuò)（HEC），是FEC和ARQ兩種方式的結(jié)合。第6章信道編碼6.1信道編碼與差錯(cuò)控制6.1.5信道編碼的發(fā)展歷程第6章信道編碼6.2有噪信道編碼定理6.2.1有噪信道編碼定理概述設(shè)離散無記憶信道的信道容量為C。只要待傳送的信息傳輸速率R<C，總可以找到一種碼長(zhǎng)為n，信息傳輸速率為R的編碼，當(dāng)

n足夠長(zhǎng)時(shí)，譯碼后錯(cuò)誤率

，

為任意大于零的小正數(shù)。反之，當(dāng)

R≥C時(shí)，任何編碼的

必大于零，當(dāng)

時(shí)，

。對(duì)于離散有記憶信道和連續(xù)信道，也有類似結(jié)論。有噪信道編碼定理也是一個(gè)理想編碼的存在性定理，它沒有具體說明如何構(gòu)造這一最佳碼，但是它對(duì)信道編碼理論與實(shí)踐具有根本性的指導(dǎo)意義。第6章信道編碼6.2有噪信道編碼定理6.2.2信道編碼設(shè)計(jì)的基本原理基于有噪信道編碼定理的信道編碼設(shè)計(jì)（1）增大信道容量

（2）降低碼率（3）增大碼長(zhǎng)基于冗余度和噪聲隨機(jī)化的信道編碼設(shè)計(jì)

冗余度是在信息流中插入冗余比特形成的，這些冗余比特與信息比特之間存在著特定的相關(guān)性。這樣，即使在傳輸過程中個(gè)別信息受損，也可以利用相關(guān)性從其他未受損的冗余比特中推測(cè)出受損比特的原貌，保證了信息的可靠性。

噪聲均化就是讓差錯(cuò)隨機(jī)化，以便更符合編碼定理的條件從而得到符合編碼定理的結(jié)果。第6章信道編碼6.2有噪信道編碼定理6.2.3編碼系統(tǒng)的性能度量信噪比誤碼率與編碼增益

香農(nóng)限第6章信道編碼6.3線性分組碼6.3.1線性分組碼的矩陣描述生成矩陣與校驗(yàn)矩陣系統(tǒng)碼第6章信道編碼6.3線性分組碼6.3.2線性分組碼的譯碼伴隨式與伴隨式譯碼伴隨式譯碼是線性分組碼的一種通用譯碼算法。在伴隨式與差錯(cuò)圖案之間建立一個(gè)一一對(duì)應(yīng)關(guān)系表，這個(gè)表稱為伴隨式譯碼表

。通過對(duì)伴隨式的計(jì)算和尋址，獲得預(yù)設(shè)的差錯(cuò)圖案，從而糾正這些差錯(cuò)圖案產(chǎn)生的差錯(cuò)。線性分組碼的另一種通用譯碼算法是標(biāo)準(zhǔn)陣列譯碼。第6章信道編碼6.3線性分組碼6.3.3漢明碼漢明碼是由RichardW.Hamming在1950年首次發(fā)現(xiàn)的一類糾正單個(gè)錯(cuò)誤的代數(shù)分組碼，在早期編碼史上具有里程碑意義。漢明碼是由校驗(yàn)矩陣定義分組碼的典型。漢明碼是完備碼。第6章信道編碼6.3線性分組碼6.3.4循環(huán)碼糾錯(cuò)碼的有效構(gòu)造和有效譯碼總希望使碼具有更精致的數(shù)學(xué)結(jié)構(gòu)或約束條件。分組性是一種約束，線性性又是對(duì)分組碼的一種約束，循環(huán)性是對(duì)分組碼的另一種約束。1957年，普蘭奇（E.Prange）在研究線性碼時(shí)找到了一個(gè)子類，它具有更多結(jié)構(gòu)特性。這類碼不但具有任意兩個(gè)碼字之和仍為碼字的特性，而且具有任意一個(gè)碼字的循環(huán)移位也是一個(gè)碼字的特性。具有這種特性的線性碼稱為線性循環(huán)碼。線性循環(huán)碼具有更精細(xì)的代數(shù)結(jié)構(gòu)，它的編譯碼電路簡(jiǎn)單且易于實(shí)現(xiàn)，因此得到了廣泛應(yīng)用。第6章信道編碼6.4卷積碼6.4.1卷積碼的基本概念

卷積碼編碼產(chǎn)生由定長(zhǎng)向量構(gòu)成的向量序列，并稱序列中的向量為分組或向量段或段，l時(shí)刻的編碼輸出段不僅與當(dāng)前的輸入段有關(guān)，而且與前

m個(gè)時(shí)刻的輸入段有關(guān)，m

稱為記憶長(zhǎng)度分組碼編碼與卷積碼編碼的基本結(jié)構(gòu)對(duì)比第6章信道編碼6.4卷積碼6.4.2卷積碼的描述線性卷積碼的矩陣描述由其前k行和前(m+1)n列組成的子矩陣完全確定，故稱為卷積碼的基本生成矩陣。的第i行行向量描述了所有各段輸入中的第i位輸入比特對(duì)所有輸出比特的影響。由線性分組碼生成矩陣特性可知，若

，則表示輸入移位寄存器的第

段的第

i位輸入比特

參與第j位輸出比特的編碼；若

，則表示不參與輸出編碼。第6章信道編碼6.4卷積碼6.4.2卷積碼的描述線性卷積碼的多項(xiàng)式描述,線性卷積碼的多項(xiàng)式生成矩陣第6章信道編碼6.4卷積碼6.3.3卷積碼的Viterbi譯碼在消息符號(hào)等概率出現(xiàn)的假設(shè)下，可以認(rèn)為卷積碼的各編碼路徑等概率出現(xiàn)，于是卷積碼的最大似然譯碼是尋找一條路徑，使似然概率

或?qū)?shù)似然值最大。卷積碼的最大似然譯碼過程是一個(gè)不斷求取幸存路徑的過程。Viterbi譯碼作為最大似然譯碼總能使譯碼錯(cuò)誤率最小，描述這一錯(cuò)誤特性的主要參數(shù)是卷積碼的自由距離。卷積碼的自由距離

是所有非零碼字路徑距離的最小值。第6章信道編碼6.5Turbo碼6.5.1Turbo碼的編碼方法編碼器由交織器、兩個(gè)遞歸系統(tǒng)卷積碼（RSC）分量編碼器、刪余器和復(fù)接器組合而成，由該編碼器生成的碼字稱為并行級(jí)聯(lián)卷積碼（PCCC）。PCCC型Turbo碼編碼器結(jié)構(gòu)第6章信道編碼6.5Turbo碼6.5.2Turbo碼的譯碼方法譯碼時(shí)將與信息序列和相應(yīng)的冗余序列對(duì)應(yīng)的接收序列分別輸入兩個(gè)譯碼器，然后各自的輸出經(jīng)過一個(gè)減法運(yùn)算獲取外信息并通過交織和解交織后反饋給另一個(gè)譯碼器。在迭代譯碼過程中，接收序列中的錯(cuò)誤不斷地被糾正。整個(gè)譯碼過程中信息在兩個(gè)極為簡(jiǎn)單的譯碼器間不斷地輪轉(zhuǎn)，像一臺(tái)無比強(qiáng)大的渦輪機(jī)，因而稱為Turbo碼。第6章信道編碼6.6LDPC碼6.6.1LDPC碼的基本概念與一般的線性分組碼不同，LDPC碼是一個(gè)具有稀疏校驗(yàn)矩陣的分組碼，相對(duì)于行與列的長(zhǎng)度，校驗(yàn)矩陣每行、列中非零元素的數(shù)目（我們習(xí)慣稱其為行重、列重）非常?。ㄕ蛉绱耍ｒ?yàn)矩陣被稱為低密度奇偶校驗(yàn)矩陣），譯碼復(fù)雜度低，長(zhǎng)碼下性能逼近香農(nóng)限。第6章信道編碼6.6LDPC碼6.6.2LDPC碼的構(gòu)造方法隨機(jī)構(gòu)造、PEG構(gòu)造、準(zhǔn)循環(huán)構(gòu)造及原模圖構(gòu)造6.6.3LDPC碼的編碼方法傳統(tǒng)編碼：若校驗(yàn)矩陣的各行都是線性無關(guān)的，通過矩陣的初等變換，就可以得到生成矩陣軟件仿真情況下采用的編碼方法：具有類似下三角形式的矩陣

的編碼方法第6章信道編碼6.6LDPC碼6.6.4LDPC碼的譯碼算法LDPC碼有多種譯碼方法，其核心思想主要是基于Tanner圖上的消息傳遞（MessagePassing，MP）算法。根據(jù)消息迭代過程中消息傳遞的不同形式，LDPC碼的譯碼算法可以分為硬判決譯碼算法和軟判決譯碼算法兩類。Gallager提出的比特翻轉(zhuǎn)（BitFlipping，BF）譯碼算法屬于硬判決譯碼算法，其計(jì)算復(fù)雜度低，但譯碼性能較差。軟判決譯碼算法的性能雖然明顯好于硬判決譯碼算法，但計(jì)算復(fù)雜度較高。和積（SumProduct，SP）算法是消息傳遞算法中的一種軟判決譯碼算法，由于傳遞的消息為節(jié)點(diǎn)的概率密度，因而又稱為置信傳播（BeliefPropogation，BP）算法。BP算法是一種較重要的消息傳遞算法，該算法通過各節(jié)點(diǎn)之間信息（也稱為概率或置信信息）的傳遞來實(shí)現(xiàn)譯碼。第6章信道編碼6.7極化碼6.7.1極化碼的基本概念與信道極化對(duì)

N個(gè)獨(dú)立的二進(jìn)制輸入信道

W，進(jìn)行所謂的信道合并操作和信道分裂操作，從而得到

個(gè)前后依賴的極化信道。這些極化信道相比原本未經(jīng)極化的信道，在和容量保持不變的情況下，每個(gè)子信道的信道容量會(huì)呈現(xiàn)出極化現(xiàn)象：一部分信道的信道容量增大，另外一部分信道的信道容量減小。并且，理論上已證明，對(duì)接近無窮多個(gè)信道進(jìn)行極化操作后，一部分信道的信道容量將趨于1（通過該部分信道傳輸?shù)谋忍匾欢〞?huì)被正確接收），而其余信道的信道容量將趨于0（完全無法在其上可靠地傳輸比特），同時(shí)，容量為1的信道占信道總數(shù)的比例正好為原二進(jìn)制輸入離散信道的信道容量

。第6章信道編碼6.7極化碼6.7.1極化碼的基本概念與信道極化這一現(xiàn)象被稱為信道極化（ChannelPolarization）。信道極化的過程由信道合并和信道分裂兩部分組成極化碼（Polar碼）是基于信道極化給出了一種編碼方式。極化碼具有確定性的構(gòu)造方法，并且是第一種，也是目前已知的唯一一種能夠被嚴(yán)格證明“達(dá)到”信道容量的信道編碼方法。第6章信道編碼6.7極化碼6.7.2極化信道的可靠性度量各個(gè)極化信道的信道容量（或等價(jià)地，傳輸錯(cuò)誤率），可以通過計(jì)算各個(gè)極化信道的巴氏參數(shù)或者采用密度進(jìn)化（DensityEvolution，DE）等工具得到。第6章信道編碼6.7極化碼6.7.3極化碼的編碼方法極化碼是一種線性分組碼，可以使用一般分組碼方式編碼是包含信息比特與凍結(jié)比特的信息序列第6章信道編碼6.7極化碼6.7.4極化碼的譯碼算法串行抵消SC譯碼算法，充分利用了極化碼的極化思想，是極化碼的主流譯碼算法的基礎(chǔ)。第6章信道編碼6.8信道編碼的應(yīng)用設(shè)計(jì)6.8.1碼的速率匹配設(shè)計(jì)碼的常見速率匹配設(shè)計(jì)分3類6種，分別是擴(kuò)展與打孔、增廣與刪信、延長(zhǎng)與縮短6.8.2碼的組合構(gòu)造方法碼的組合構(gòu)造方法主要有乘積、交織、級(jí)聯(lián)和

構(gòu)造。另外，還有復(fù)制、笛卡兒積、直積、直和、鏈接等。第6章信道編碼THEEND!信息論與編碼第7章保密編碼7.1密碼通信的基本模型7.1.1通信模型7.1.2密碼體制的基本要求7.1.3常見的威脅7.1.4保密系統(tǒng)的安全性測(cè)度第7章保密編碼7.1.1通信模型香農(nóng)從概率統(tǒng)計(jì)的觀點(diǎn)出發(fā)研究信息的傳輸和保密問題，將通信系統(tǒng)歸納為圖7.1所示的原理圖，將保密系統(tǒng)歸納為圖7.2所示的原理圖。通信系統(tǒng)設(shè)計(jì)的目的是在信道有干擾的情況下，使接收的信息無誤或差錯(cuò)盡可能小。保密系統(tǒng)設(shè)計(jì)的目的是使竊聽者（或攻擊者）即使在完全準(zhǔn)確地收到了接收信號(hào)的情況下也無法恢復(fù)出原始信息。圖7.1通信系統(tǒng)原理圖圖7.2保密系統(tǒng)原理圖7.1.1通信模型在保密系統(tǒng)中，信源是信息的發(fā)送者，離散信源可以產(chǎn)生字符或字符串。設(shè)信源的字母表，即明文字母表為其中，為正整數(shù)，表示明文字母表中字母的個(gè)數(shù)。字母出現(xiàn)的概率記為，，，并且。若只考慮長(zhǎng)為的信源輸出，則明文空間為（7-1-1）若信源是無記憶的，則（7-1-2）若信源是有記憶的，則需要考慮明文空間中各元素的概率分布。7.1.1通信模型密鑰產(chǎn)生于密鑰源，密鑰源通常是離散的。設(shè)密鑰源字母表為，其中，表示密鑰源字母表中字母的個(gè)數(shù)。字母是正整數(shù)，出現(xiàn)的概率記為密鑰源通常是無記憶的，并且一般服從均勻分布，因此（7-1-3）（7-1-4）7.1.1通信模型由于密文空間與明文空間是相互獨(dú)立的，所以對(duì)于任意的，有（7-1-5）又由于，所以根據(jù)Bayes公式可得（7-1-6）7.1.1通信模型由此可以看出，知道明文空間和密鑰空間的概率分布，就可確定密文空間的概率分布、密文空間關(guān)于明文空間的概率分布，以及明文空間關(guān)于密文空間的概率分布。在保密系統(tǒng)中，如果假定信道是無干擾的，則合法的密文接收者能夠利用解密變換和密鑰從密文中恢復(fù)明文，如果假定密碼分析者能夠從信道上截獲密文，還假定密碼分析者知道所有的密碼體制，且知道明文空間和密鑰空間及其統(tǒng)計(jì)特性（這就是所謂的Kerckhoffs假設(shè)，也即所謂的Kerckhoffs原則（KerckhoffsPrinciple），那么密碼體制的安全性完全取決于所選用的密鑰的安全性，也即如果攻擊者不知道密文所用的密鑰，在Kerckhoffs原則下，密碼算法的安全性完全寓于密鑰的安全性之中。7.1.2密碼體制的基本要求密碼學(xué)分支：密碼編碼學(xué)：研究和設(shè)計(jì)各種密碼體制，確保信息安全隱藏。密碼分析學(xué)：在不知道密鑰的情況下分析和破譯密碼，以獲取隱藏的信息。密碼體制的目標(biāo)：隱藏和偽裝信息，防止未授權(quán)訪問。香農(nóng)的五項(xiàng)準(zhǔn)則：系統(tǒng)的保密強(qiáng)度：最關(guān)鍵的準(zhǔn)則，涉及密碼體制能否在給定的應(yīng)用需求下保持信息的機(jī)密性。密鑰的規(guī)模：關(guān)系到密鑰的管理和安全性，隨著技術(shù)的進(jìn)步，對(duì)密鑰規(guī)模的限制已經(jīng)放寬。加密和解密運(yùn)算的簡(jiǎn)易性：現(xiàn)代密碼體制借助高性能計(jì)算設(shè)備，可以處理復(fù)雜的數(shù)學(xué)運(yùn)算，但操作的復(fù)雜性仍需控制。錯(cuò)誤的擴(kuò)散程度：在密文傳輸中出現(xiàn)錯(cuò)誤時(shí)，應(yīng)盡量減少錯(cuò)誤擴(kuò)散，以防連鎖反應(yīng)。信息的擴(kuò)散程度：在加密過程中應(yīng)盡量減少信息的擴(kuò)散，以保持傳輸效率和減少傳輸成本。7.1.2密碼體制的基本要求系統(tǒng)的保密強(qiáng)度理論保密vs.實(shí)際保密：理論保密（絕對(duì)安全）：假設(shè)密碼分析者擁有無限資源，但仍無法破譯。實(shí)際保密（計(jì)算性安全）：假設(shè)密碼體制的破譯需要超過實(shí)際可行的資源或時(shí)間。密鑰的規(guī)模和管理密鑰管理的挑戰(zhàn)：密鑰需要安全傳輸和存儲(chǔ)，且有時(shí)需依靠記憶保持安全。一密一鑰體制：理論上完全安全，但實(shí)際上可能因密鑰傳輸被截獲而變得脆弱。加密和解密運(yùn)算的實(shí)際應(yīng)用早期體制的限制：手工操作易錯(cuò)，機(jī)械設(shè)備昂貴且復(fù)雜?，F(xiàn)代技術(shù)的優(yōu)勢(shì)：使復(fù)雜運(yùn)算可行，但應(yīng)避免過度復(fù)雜以保證用戶可接受。錯(cuò)誤與信息的擴(kuò)散錯(cuò)誤的擴(kuò)散：盡量減少，特定情況下可用于信息認(rèn)證。信息的擴(kuò)散：控制信息在加密過程中的擴(kuò)散，優(yōu)化傳輸速率和成本。7.1.3常見的威脅Kerckhoffs原則簡(jiǎn)介：假設(shè)密碼分析者已知密碼體制的所有細(xì)節(jié)，除了加密使用的密鑰。密碼體制的安全性不應(yīng)依賴于算法的保密性，而應(yīng)依賴于密鑰的保密性。任何好的密碼算法都應(yīng)能承受公開討論而不泄露密鑰信息。常見的密碼攻擊方法唯密文攻擊：最弱的攻擊類型，分析者僅有密文，需嘗試恢復(fù)明文或密鑰。依賴于對(duì)系統(tǒng)和消息語言的一般了解。已知明文攻擊：攻擊者已知部分明文和對(duì)應(yīng)的密文。目標(biāo)是推導(dǎo)出密鑰或能解密新密文的算法。選擇性明文攻擊：攻擊者可以選擇明文，獲取對(duì)應(yīng)密文。相比已知明文攻擊更有效，因?yàn)楣粽呖刂萍用苓^程。自適應(yīng)選擇明文攻擊：攻擊者基于之前的加密結(jié)果，適應(yīng)性地選擇新的明文進(jìn)行加密。需要的明文和密文對(duì)更少，比選擇性明文攻擊更高效。選擇性密文攻擊：攻擊者可以選擇要解密的密文，嘗試恢復(fù)明文。適用于公鑰和私鑰體制，計(jì)算復(fù)雜性與選擇性明文攻擊相當(dāng)。選擇性密鑰攻擊：攻擊者知道一些密鑰之間的關(guān)系，嘗試?yán)眠@些關(guān)系解密。不是實(shí)際操作的常規(guī)方法，但在理論上對(duì)某些體制是有效的。7.1.3常見的威脅攻擊的復(fù)雜性衡量數(shù)據(jù)復(fù)雜性：解密所需的數(shù)據(jù)量，包括密文、明文及其對(duì)。時(shí)間復(fù)雜性：完成解密所需的計(jì)算時(shí)間。空間復(fù)雜性：解密過程中所需的存儲(chǔ)空間。攻擊方法的有效性和實(shí)用性依賴于可用資源和已知信息的多少。密碼體制的設(shè)計(jì)應(yīng)考慮最高級(jí)別的攻擊防御，以確保長(zhǎng)期安全。7.1.4保密系統(tǒng)的安全性測(cè)度差分功耗分析（DifferentialPowerAnalysis，DPA）攻擊，使密碼攻擊所需的數(shù)學(xué)推導(dǎo)和計(jì)算量大幅度降低，給密碼算法的實(shí)際安全帶來了嚴(yán)重的威脅圖7.2保密系統(tǒng)原理圖（7-1-7a）或從密文中提取密鑰信息：（7-1-7b）7.1.4保密系統(tǒng)的安全性測(cè)度說明合法用戶在掌握密鑰并已知密文的情況下，可以提取全部明文信息。定理7.1

對(duì)任意保密系統(tǒng)，有證明：由熵的性質(zhì)可導(dǎo)出考慮到故有即保密算法的密鑰空間越大，破譯越困難。7.1.4保密系統(tǒng)的安全性測(cè)度說明合法用戶在掌握密鑰并已知密文的情況下，可以提取全部明文信息。定理7.1

對(duì)任意保密系統(tǒng)，有證明：由熵的性質(zhì)可導(dǎo)出考慮到故有即保密算法的密鑰空間越大，破譯越困難。7.2古典密碼7.2.1單表密碼7.2.2多表密碼7.2.3換位密碼7.2.4線性反饋移位寄存器密碼第7章保密編碼7.2.5序列密碼和分組密碼7.2.1單表密碼1．加法密碼在這種密碼中，明文消息中的每個(gè)字母均用在它后面的第三個(gè)字母（按正常字母表順序）來代換，這種代換關(guān)系如表7.1所示，表中正常順序的明文字母表，用小寫字母表示；循環(huán)左移三個(gè)字母的密文字母表，用大寫字母表示，在第一行上，按正常字母排列，附上對(duì)應(yīng)的1～26的對(duì)應(yīng)的數(shù)字編號(hào)。明文：chengduinstituteofradioengineering密文：FKHQJGXLQVWLWXWHRIUGIRHQJLQHHULQJ7.2.1單表密碼數(shù)學(xué)模型凱撒密碼加密變換的數(shù)學(xué)模型為同樣，凱撒密碼解密變換的數(shù)學(xué)模型為7.2.1單表密碼2．乘法密碼加法密碼的代換字母表是通過將字母移位產(chǎn)生的。另外，這種代換字母表還可以通過正常字母表的等間隔抽取來獲得，即乘法密碼的加密變換的數(shù)學(xué)模型為（7-2-5）其中滿足，也就是說必須是和26互素的任意整數(shù)。只有當(dāng)成立時(shí)，按式（7-2-5）進(jìn)行的變換才是從明文空間到密文空間的一一對(duì)應(yīng)的變換。由于此類變換是按照同余乘法來完成的，故稱為乘法密碼。在乘法密碼中，密鑰就是乘數(shù)滿足條件的取值為：＝1,3,5,7,9,11,13,15,17,21,23,25共12個(gè)數(shù)，且當(dāng)＝1時(shí)，產(chǎn)生恒等密碼。故有效的乘法密碼的密鑰只有11種。7.2.1單表密碼3．仿射密碼將上述加法密碼和乘法密碼相結(jié)合，可以得到擁有更多密鑰的新的密碼。從加密變換的數(shù)學(xué)模型上看，即將加同余和乘同余進(jìn)行如下的線性同余變換：（7-2-7）從構(gòu)成方法上看，式（7-2-7）實(shí)際上是等間隔（）抽取和移位（）相結(jié)合，稱此類密碼為仿射密碼。7.2.1單表密碼4．隨機(jī)代換密碼在前述幾種代換密碼中，代換字母表是由正常順序字母表按某種簡(jiǎn)單規(guī)律變換而得的，具有便于記憶的優(yōu)點(diǎn)，但缺點(diǎn)是密鑰量小、保密強(qiáng)度低。如果代換字母表是由26個(gè)字母隨機(jī)抽取排列而成的（見表7.4），則總共有26！種不同的排列順序，即共有26！種不同的密鑰。通過計(jì)算可知，26！近似等于4×1026，密鑰量非常大。從密鑰量上而言，可以大大提高系統(tǒng)的保密性。那么，這類密碼體制的加密、解密密鑰的保管，就變得非常重要。否則，一旦密鑰丟失，就會(huì)造成泄密，而且發(fā)送者會(huì)無法實(shí)現(xiàn)加密，接收者無法正確解密。為了保留隨機(jī)代換密碼的密鑰量大的優(yōu)點(diǎn)，同時(shí)又克服密鑰不便于記憶的缺點(diǎn)，密鑰詞組密碼被提出。7.2.1單表密碼5．密鑰詞組換密碼可以任意選擇一個(gè)詞組來作為密鑰，構(gòu)成代換字母表，方法如下。首先，寫出正常順序的密文字母表，從特定的字母（該特定字母也作為密鑰的一個(gè)組成部分）開始寫出密鑰詞組，但要?jiǎng)h除密鑰詞組中的重復(fù)字母（以保證一一對(duì)應(yīng)的代換）。例如，選擇monoalphabeticcipher作為密鑰詞組，刪除重復(fù)的字母得到monalphbeticr，選擇字母e作為開始書寫密鑰詞組的特定字母，則得到表7.5所示的密碼表。7.2.1單表密碼5．密鑰詞組換密碼然后，將未出現(xiàn)在密鑰詞組中的其他字母，按照字母順序，填寫在密鑰詞組之后，當(dāng)在z字母下填寫了字母后，再接著填寫到a字母下面，直至完成了包含密鑰詞組的代換字母表，如表7.6所示。由于密鑰詞組和特定字母可以任意選擇，因此可以構(gòu)成的代換字母表的數(shù)量是極大的（當(dāng)然不會(huì)超過26！），足以對(duì)付密碼分析者用窮舉法進(jìn)行的攻擊。同時(shí)，密鑰詞組和特定字母可以隨意選擇，且又易于記憶，故此類密碼既克服了隨機(jī)代換密碼的密鑰表不便于記憶的缺點(diǎn)，又保留了密鑰量大的優(yōu)點(diǎn)。7.2.1單表密碼6．密碼分析方法盡管隨機(jī)代換密碼和密鑰詞組密碼可能產(chǎn)生的密鑰數(shù)量極大，利用窮舉法進(jìn)行密碼分析難以奏效。但它們均屬于單表密碼，是利用字母的一一對(duì)應(yīng)的代換實(shí)現(xiàn)對(duì)明文的加密的，因而明文所用語言的各種統(tǒng)計(jì)特性都會(huì)反映到密文中。這樣，只要所截獲的明文具有適當(dāng)?shù)拈L(zhǎng)度，足以反映出所用語言的某些統(tǒng)計(jì)特性，利用統(tǒng)計(jì)方法就可以很快破譯出這類單表密碼。在英文的26個(gè)字母中，各字母出現(xiàn)的相對(duì)概率是不一樣的，各字母出現(xiàn)的相對(duì)概率是穩(wěn)定的，而且完全可以預(yù)測(cè)，如下表所示。由表7.7可知，字母g出現(xiàn)的相對(duì)概率最高。因此，在單表密碼中，只要密文具有適當(dāng)長(zhǎng)度，那么出現(xiàn)頻率最高的字母幾乎肯定就是英文字母h的等價(jià)密文字母。7.2.2多表密碼在單表密碼中，每個(gè)密文字符唯一地代替了一個(gè)明文字符。因此，在明文中，各字母和常用字母組合出現(xiàn)的概率等統(tǒng)計(jì)規(guī)律，必然同樣地反映在密文中，密碼分析者可以利用語言的統(tǒng)計(jì)特性成功地破譯各種單表密碼。因此，如果一個(gè)明文字母可用多個(gè)密文字母代替，那么明文字母中的統(tǒng)計(jì)特性就不至于全部反映在密文中，從而提高密文的抗攻擊性，這類密碼體制稱為多表密碼體制。信息加密的一個(gè)基本要求，就是一篇密文只能唯一地被譯成一篇確定的明文，反之亦然。而在多表密碼體制中，一個(gè)密文字母可能代表多個(gè)明文字母，而究竟應(yīng)該是哪個(gè)明文字母，則必然與該字母在密文中的位置和所給定的密鑰有關(guān)，可以根據(jù)密鑰的指示和密文字母的位置，將密文字母唯一地譯成它的等價(jià)明文字母。實(shí)現(xiàn)上述思路的方案較多，最著名的就是維吉尼亞密碼，由法國密碼學(xué)家維吉尼亞提出。它利用了表7.8所示的維吉尼亞方陣來實(shí)現(xiàn)對(duì)明文的加密。7.2.2多表密碼7.2.2多表密碼由表7.8可知，基本方陣是26×26的，在表的頂上附加一行，左邊附加一列，分別依次寫上從a至z的26個(gè)字母。表的第一行與附加列上的字母a相對(duì)應(yīng)，按正常順序從A排列至Z；第二行與附加列上的字母b相對(duì)應(yīng)，是上一行向左循環(huán)移動(dòng)一位而成的。以此類推，得到了維吉尼亞方陣。加密時(shí)，到底采用哪一個(gè)“單表”，則要按照密鑰的指示，到最左邊的附加列上找到對(duì)應(yīng)的字母后，就用該行密碼表進(jìn)行單表代換。多表密碼和單表密碼相似，加密可以用同余方程來表示：（7-2-8）7.2.3換位密碼換位密碼又稱為轉(zhuǎn)置密碼，在加密方式和密文形式上均不同于前面所述的代換密碼。這類密碼體制的加密，并未改變明文消息所含的字母本身，而只是對(duì)明文消息所含的全部字母在文中的位置進(jìn)行重新排列?？梢圆捎枚喾N不同的方法，實(shí)現(xiàn)對(duì)明文消息所含的字母的重新排列。如果需要傳送如下明文：transpositioncipher，則可以按照以下幾種簡(jiǎn)單的方法對(duì)明文字母加以重排。1．倒序密碼該密碼顛倒字母書寫順序，即從尾至首依次書寫，且每5個(gè)字母寫為一組，得密文：REHPICNOITISOPSNART2．柵欄密碼該密碼將明文字母交替書寫在兩行上，按行讀出即為密文。3．圖形密碼該密碼是先選定一種幾何圖形，然后按照一種確定的路線或書寫方向，將明文消息書寫到該圖形上，最后按第二種路線寫出上面消息即可獲得密文。4．列轉(zhuǎn)置密碼在換位密碼中，比較有代表性的是列轉(zhuǎn)置密碼。該密碼方案加密的基本思路是將明文消息逐行寫到一個(gè)事先規(guī)定了寬度（列數(shù)）的矩形中，再按列讀出，即構(gòu)成密文。顯然，為了提高保密性，在從矩形中提取密文時(shí)，不應(yīng)該從左至右依序讀取各列，而應(yīng)該按隨機(jī)次序讀取，但同時(shí)又要方便記憶。一般是選取一個(gè)密鑰，即決定了書寫明文時(shí)的矩形寬度（列數(shù)），又決定了讀取各列時(shí)的先后次序。7.2.4線性反饋移位寄存器密碼n級(jí)線性反饋移位寄存器如圖7.3所示。圖7.3n級(jí)線性反饋移位寄存器7.2.4線性反饋移位寄存器密碼決定了移位寄存器的反饋抽頭情況，它的第一行為抽頭序列，在主角線下面恰好為1其他位置均為0。7.2.4線性反饋移位寄存器密碼線性反饋移位寄存器的破譯按下式可以計(jì)算出密鑰序列

：7.2.4線性反饋移位寄存器密碼令X和Y為由于線性反饋移位寄存器的線性特性，矩陣X和Y具有以下關(guān)系因?yàn)閄總是為非奇異矩陣，故有線性反饋移位寄存器的上述弱點(diǎn)，是由于它的線性特性引起的。為了克服此弱點(diǎn)，使它在密碼技術(shù)中獲得實(shí)際應(yīng)用，一般采用以下兩種改進(jìn)方案：一種是在移位寄存器中引入非線性邏輯；另一種是在反饋邏輯中使用非線性器件。7.2.5序列密碼和分組密碼1．分組密碼的定義7.2.5序列密碼和分組密碼2．序列密碼的定義7.2.5序列密碼和分組密碼3．兩種密碼的聯(lián)系周期較短的周期性代換密碼（如維吉尼亞密碼）通常被看作序列密碼，因?yàn)槠鋵?duì)明文字符是逐個(gè)加密的，且相鄰字符又利用密鑰的不同部分進(jìn)行加密，因而其兼有兩類密碼的特征。令密鑰序列，這里為密碼的周期。即密鑰序列可以表示為當(dāng)周期較短時(shí)，這種密碼更像分組密碼，不過它是一種保密強(qiáng)度很弱的分組密碼；隨著周期長(zhǎng)度的增加，這類密碼變得更像序列密碼。7.3數(shù)據(jù)加密標(biāo)準(zhǔn)DES7.3.1DES算法基本原理7.3.2DES算法運(yùn)算過程7.3.3DES算法的弱點(diǎn)第7章保密編碼7.3.1DES算法基本原理DES算法是一種分組加密算法，也是一種對(duì)稱算法，即加密和解密用的是同一種算法（除密鑰編排不同）。DES算法最重要的特點(diǎn)是，其加密和解密過程，以及密鑰加工過程都是公開的，其安全性主要依賴于密鑰的復(fù)雜性。圖7.6給出了DES算法的主要結(jié)構(gòu)圖7.6DES算法的主要結(jié)構(gòu)7.3.2DES算法運(yùn)算過程DES算法把64位的明文輸入塊變?yōu)?4位的密文輸出塊，所使用的密鑰也是64位的，DES算法對(duì)64位的明文分組進(jìn)行操作。通過一個(gè)初始置換，首先將明文分組分成左半部分和右半部分，各長(zhǎng)32位。然后進(jìn)行16輪相同的運(yùn)算，這些相同的運(yùn)算被稱為函數(shù)，在運(yùn)算過程中數(shù)據(jù)和密鑰相結(jié)合。經(jīng)過16輪運(yùn)算后，左、右部分合在一起經(jīng)過一個(gè)置換（初始置換的逆置換），再輸出，則算法完成。1．初始置換（IP）初始置換功能是將輸入的64位數(shù)據(jù)塊按位重新組合，并把輸出分為L(zhǎng)0、R0兩部分，每部分各長(zhǎng)32位，其置換規(guī)則如表7.13所示。由表7.13可知，初始置換將輸入的第58位換到第1位，第50位換到第2位，以此類推，最后1位是原來的第7位。7.3.2DES算法運(yùn)算過程2．密碼運(yùn)算通過初始置換后，算法在密鑰控制下進(jìn)行16次迭代運(yùn)算，每次迭代都進(jìn)行同樣的操作?？梢员硎緸镈ES算法的密碼運(yùn)算結(jié)構(gòu)如圖7.7所示，該部分為DES算法的核心內(nèi)容，該部分主要是密碼計(jì)算函數(shù)。圖7.7DES算法的密碼運(yùn)算結(jié)構(gòu)7.3.2DES算法運(yùn)算過程2．密碼運(yùn)算擴(kuò)充函數(shù)E是將32位數(shù)據(jù)放大成48位數(shù)據(jù)，的第i位作為第j位輸出。擴(kuò)充函數(shù)E的擴(kuò)充規(guī)則如表7.14所示。P函數(shù)，又稱為換位函數(shù)，簡(jiǎn)稱P盒。P盒是32位數(shù)據(jù)到32位數(shù)據(jù)的換位，其換位規(guī)則如表7.15所示。7.3.2DES算法運(yùn)算過程2．密碼運(yùn)算S函數(shù)，又稱為替代函數(shù)，簡(jiǎn)稱S盒，其功能是把6位數(shù)據(jù)變?yōu)?位數(shù)據(jù)。具體規(guī)則如下。（1）將6位數(shù)中的第1、6位組成的二進(jìn)制數(shù)作為行號(hào)。（2）將第2、3、4、5位組成的二進(jìn)制數(shù)作為列號(hào)。（3）尋找替代函數(shù)功能表的行、列交叉處，即為要輸出的4位數(shù)。下面以替代函數(shù)