信息論與編碼全套課件電子教案板

信息論與編碼第一部分信息論基礎(chǔ)（第一章‐第五章）從學科方向說起信息科學信息與通信工程電子科學與技術(shù)計算機科學與技術(shù)控制科學與技術(shù)。。。信息產(chǎn)業(yè)的兩大支柱：通信+計算機信息與通信工程：研究信息有效獲取、表達、存儲、傳輸與處理的系統(tǒng)科學與工程技術(shù)；信息論——信息科學發(fā)展的源泉和動力信息論信息科學發(fā)展的思想源泉和動力通信與信息系統(tǒng)的基礎(chǔ)理論信息論與通信原理、通信技術(shù)前者：揭示信息獲取、表達、傳輸與處理等過程所包含的本質(zhì)規(guī)律與所應遵循的基本設計原則后者：具體環(huán)境和條件下通信過程的基本原理、具體實現(xiàn)方法、手段和技術(shù)信息論與現(xiàn)代信號處理理論虛實相生、相輔相成現(xiàn)代通信與信息系統(tǒng)研究與實現(xiàn)的兩大理論支柱經(jīng)典信息論所研究的若干基本問題信源編碼問題信息是什么？理論上至少應該以什么樣的速率才能無差錯地表達一個信源所包含的信息？信道編碼問題給定一個信道，理論上通過該信道最多能以多大的速率無差錯地傳遞信息？……Shannon的回答信源編碼當編碼速率大于信源的熵速率即可實現(xiàn)漸進無差錯地表達信道編碼當傳信率比信道容量高時，必然發(fā)送差錯，反之，則可以實現(xiàn)漸進無差錯地傳輸信息論革命性的指導意義（I）奠定了通信的基礎(chǔ)理論，它所確定的理論極限是人類追求的目標，也是近代幾乎所有通信技術(shù)取得重大突破的理論動力和思想源泉也帶動了整個信息科學的發(fā)展，產(chǎn)生了很多信息科學的邊緣學科和交叉學科，例如量子信息論，生物信息學，等等現(xiàn)代信息論蓬勃發(fā)展，導致網(wǎng)絡通信、多用戶通信、分布式通信、極限通信等許多學科方向的發(fā)展，新理論與新技術(shù)日新月異，層出不窮信息論革命性的指導意義（II）1993年，受Shannon隨機編碼思想的啟示，C.Berrou等人提出了著名的基于交織級聯(lián)和迭代譯碼的Turbo碼，首次獲得了逼近Shannon容量極限的性能，這一里程碑式的重大突破奠定了第三代無線移動通信的基礎(chǔ)。1999年，D.J.Mackay等人重新發(fā)掘出R.G.Gallager早期研究的LDPC碼，并且發(fā)現(xiàn)在迭代譯碼的方式下這也是一類能夠逼近Shannon極限的好碼。隨機編碼與迭代譯碼一時被認為是逼近Shannon極限的最為實用和有效的方法。信息論革命性的指導意義（III）1995年，I.E.Telatar第一次將單天線高斯信道的容量理論推廣到多天線的情形，由此獲得了一個令人震驚的結(jié)論：一定條件下，信道容量可隨天線數(shù)目的增加而同比例增大，由此奠定了多天線（MIMO）通信理論的基礎(chǔ)。隨著BellLabs的實驗證實和不斷完善，多天線技術(shù)正式成為第三代/第四代無線通信實現(xiàn)容量增強不可或缺的核心技術(shù)。它同時也在理論上極大地豐富了經(jīng)典Shannon信息論，并成為現(xiàn)代信息論中一個活躍的分支——多端網(wǎng)絡的重要研究方向。信息論革命性的指導意義（IV）本世紀初信息與編碼理論領(lǐng)域最激動人心的突破來自于華人學者RaymondYeung，NingCai和RobertLi及其合作者，這就是著名的網(wǎng)絡編碼理論。他們通過改變網(wǎng)絡節(jié)點的簡單存儲轉(zhuǎn)發(fā)方式，而進行適當?shù)木幋a轉(zhuǎn)發(fā)，即可獲得網(wǎng)絡流的最小割容量，從而大大提升網(wǎng)絡多播的效率。如今，網(wǎng)絡編碼已經(jīng)形成了一個龐大的編碼理論體系，涉及到網(wǎng)絡源編碼、網(wǎng)絡內(nèi)容分送(組播、P2P等)、網(wǎng)絡糾錯、網(wǎng)絡保密的各個方面，受到全球眾多研究機構(gòu)的關(guān)注和研究。這是華人學者為世界所作出的開創(chuàng)性貢獻。1948年香農(nóng)創(chuàng)立信息論信息論之父（比特之父）ClaudeElwoodShannon

1916.4.30-2001.2.24C.E.Shannon——信息論之父，比特之父

20歲從密歇根大學畢業(yè)；22歲在MIT獲碩士，24歲獲博士隨后在BellLab.從事通信、密碼、計算機等領(lǐng)域研究

1945年“保密的數(shù)學理論”；

32歲（1948年）“通信的數(shù)學理論”；

1956年回到MIT，重新研究信息論，在他下面集聚了一批年青學者和研究生，F(xiàn)ano,Elias,Gallager,Berlekamp,Forney,Ziv,Massey,Wyner,…，建立和發(fā)展了Shannon意義下信息論。

提出了信息量的精確定義和度量－熵和“比特”信源編碼定理，信道編碼定理，率失真定理；信道和信源分離編碼定理；多用戶信息理論（雙向通信理論，反饋通信，發(fā)射端具有邊信息的通信）；開關(guān)電路與布爾代數(shù)；保密的數(shù)學理論；人工智能（計算機下棋）；方法學上：典型列理論；隨機編碼理論；C.E.Shannon的偉大成就Ihaveoftenremarkedthatthetransistorandinformationtheory,twoBellLaboratoriesbreakthroughswithinmonthsofeachother,havelaunchedandpoweredthevehicleofmoderndigitalcommunications.Solidstateelectronicsprovidedtheenginewhileinformationtheorygaveusthesteeringwheelwithwhichtoguideit.

A.Viterbi對信息論的評價本課程的定位本課程是信息科學領(lǐng)域電子信息類專業(yè)的重要專業(yè)基礎(chǔ)課程，主要用以了解和認識一般通信與信息系統(tǒng)的基本概念、本質(zhì)規(guī)律與性能極限，并掌握其基本的設計方法和原則，為進一步深入學習和研究通信與信息系統(tǒng)的新理論與新技術(shù)、學習和研究多用戶信息論與網(wǎng)絡信息論奠定基礎(chǔ)。本課程的研究內(nèi)容主要介紹信息的基本概念與度量方法、信源無損壓縮及其編碼定理、信道容量及信道編碼定理、率失真理論等內(nèi)容緒論（1學時）信息的概念和度量：熵和互信息（7學時）離散無記憶信源的無損壓縮編碼（8學時）信道、信道容量與信道編碼定理（11學時）率失真理論與限失真信源編碼（7學時）本課程的基本要求重點掌握信息的基本概念和基本定理的內(nèi)涵，了解信息論的重要思想與方法，關(guān)注信息論的典型應用課程評價方法：作業(yè)與平時成績（含點名）：20%考試成績：80%本課程的教材和參考書仇佩亮，《信息論與編碼》，高等教育出版社，“十五”國家級規(guī)劃教材，2003年第一版T.M.Cover，《ElementsofInformationTheory》，thesecondedition,Wiley，2006.第二章熵與互信息符號系統(tǒng)X,Y：隨機變量（待觀測變量）xk

,

yj

:變量取值（觀測值）ak,bj:變量取值（觀測值）

X={xk;k=1,2,…,K};Y={yj;j=1,2,…,J}:變量值域事件：X=xk或X=ak

;Y=yj或Y=bjqk=Pr{X=xk},wj=Pr{Y=yj}概率論基礎(chǔ)知識對聯(lián)合變量對（二維隨機矢量）

有：

事件的自信息事件的發(fā)生通常會對外界提供信息。人們對信息的感受與事件發(fā)生的概率密切相關(guān)我們將特定事件X=xk發(fā)生后給外界帶來的信息量定義為該事件的自信息當對數(shù)的底a取為2時，自信息的單位為比特（bit）；當對數(shù)底取為e時，單位稱為奈特（nat）。公理化的定義事件自信息的本質(zhì)事件發(fā)生后對外界（觀察者）所提供的信息量事件發(fā)生前外界（觀察者）為確證該事件的發(fā)生所需要的信息量，也是外界為確證該事件所需要付出的代價事件的自信息并不表示事件的不確定性，事件本身沒有不確定性可言，它要么是觀察的假設和前提，要么是觀察的結(jié)果事件的條件自信息聯(lián)合變量：事件

發(fā)生的條件下事件的條件自信息定義為：事件Y=yj

發(fā)生后事件X=xk的發(fā)生還能再給外界提供的“新”的信息量事件的聯(lián)合自信息聯(lián)合變量：所對應的事件

和聯(lián)合發(fā)生所帶來的聯(lián)合自信息定義為：事件X=xk與事件Y=yj同時發(fā)生對外界提供的信息量事件的互信息聯(lián)合變量：所對應的事件

和相互之間所提供的互信息定義為：事件互信息的本質(zhì)事件X=xk發(fā)生后提供給外界的信息量事件Y=yj發(fā)生后事件X=xk還能提供給外界的新信息量事件Y=yj中包含的有關(guān)事件X=xk信息量事件互信息的性質(zhì)事件的條件互信息

事件Z=z已知的條件下事件X=x與事件Y=y相互提供的信息量事件的聯(lián)合互信息事件Y=y和Z=z聯(lián)合提供的有關(guān)事件X=x的信息量事件聯(lián)合互信息的鏈式法則事件Y=y和Z=z聯(lián)合提供的有關(guān)事件X=x的信息量，等于Y=y提供的有關(guān)事件X=x的信息量再加上事件Y=y已知的條件下事件Z=z所提供的有關(guān)X=x的新信息量。變量的平均自信息——熵

我們更關(guān)心變量在其取值集合總體上平均每次觀測所能獲得的信息量熵的本質(zhì)（I）p10.510H(p)p越接近于0或者1（X確定性越高），熵越??；p越接近于0.5（X越不確定），熵越大熵的本質(zhì)（II）熵是隨機變量不確定性的度量熵是隨機變量每次觀察結(jié)果平均對外界所提供的信息量熵是為了確證隨機變量的取值外界平均所需要的與之相關(guān)的信息量條件熵以事件Y=y為條件的變量X的熵以變量Y為條件的變量X的熵

疑義度：Y已知的條件下X的剩余不確定性聯(lián)合熵

隨機變量X和Y的聯(lián)合熵（聯(lián)合不確定性）聯(lián)合熵的鏈式法則熵的性質(zhì)（I）熵的性質(zhì)（II）熵的性質(zhì)（III）X2={A1,A2,A3,B1,B2}X1={A,B}（5）可加性熵的性質(zhì)（IV）對變量X可以進行多步分層的觀察，每一步都可從上一步觀察結(jié)果中得到更為細致的結(jié)果，變量X在最后的觀察結(jié)果集合中的不確定性等于第一次觀察結(jié)果的不確定性，加上其后每次觀察結(jié)果在前一次觀察結(jié)果已知的前提下的條件不確定性熵的性質(zhì)（V）（6）極值性證明：對任何概率矢量q均成立。因為：（因）

令即得。熵的性質(zhì)（VI）（7）凸性授課小結(jié)事件的自信息，條件自信息，聯(lián)合自信息事件聯(lián)合自信息的鏈式法則熵的概念及其本質(zhì)條件熵，聯(lián)合熵，聯(lián)合熵的鏈式法則熵的性質(zhì)作業(yè)復習授課內(nèi)容預習2.1.5至2.2.2節(jié)獨立完成習題（每章交一次）2.12.22.42.52.6凸函數(shù)（下凸函數(shù),ConvexFunction）凹函數(shù)（上凸函數(shù),ConcaveFunction）非負凸集上的上凸函數(shù)取極大值的充要條件概率空間上的上凸函數(shù)取極大值的充要條件隨機變量間的平均互信息二個事件X=x與Y=y之間的相互提供的信息量定義為聯(lián)合隨機變量{(X,Y),X

Y,p(x,y)}相互提供的平均信息量稱之為二者之間的平均互信息，簡稱互信息：互信息的性質(zhì)（I）

（1）非負性證明：互信息的性質(zhì)（II）（2）對稱性（3）互信息與熵的關(guān)聯(lián)性互信息的性質(zhì)（III）（4）互信息與熵的大小關(guān)系

等號成立的條件是Y是X的確定性函數(shù)。等號成立的條件是X是Y的確定性函數(shù)；隨機變量間的條件互信息在隨機變量Z已知的條件下變量X與Y相互提供的信息量為隨機變量間的聯(lián)合互信息及鏈式法則隨機變量Y和Z共同提供給變量X的信息量為例：互信息的應用有兩個硬幣，一個是真幣（一面國徽，一面面值），另一個是假幣（兩面都是面值）。隨機抽取一個硬幣，拋擲2次。問出現(xiàn)面值的次數(shù)對于硬幣的識別提供多少信息？XY1/41/21/4101120X=0，真幣；X=1，假幣。Y=面值出現(xiàn)的次數(shù)1/21/21/81/45/8例：互信息的應用（續(xù)）XY1/41/21/4101120相對熵（散度）定義在相同字符表X上的兩個概率分布{p(x)}和{q(x)}之間的相對熵（散度），或稱Kullback-Leibler距離，表示為：表示實際分布{p(x)}與假定分布{q(x)}之間的平均差距，因而也稱鑒別熵。相對熵的性質(zhì)（1）（2）（3）關(guān)于疑義度的Fano不等式（I）關(guān)于疑義度的Fano不等式（II）證明：授課小結(jié)隨機變量間的平均互信息的定義互信息的性質(zhì)相對熵的定義和性質(zhì)關(guān)于疑義度的Fano不等式（重點）作業(yè)復習授課內(nèi)容預習2.1.6至2.2.2節(jié)獨立完成習題（每章交一次）2.92.102.122.132.17馬爾可夫鏈（I）p(x2|x1)p(xn|xn-1)X1X2p(x3|x2)X3Xn-1Xn

馬爾可夫鏈（II）性質(zhì)：XYZ數(shù)據(jù)處理定理XYZ證明：由于故四變量馬爾可夫鏈UXYV證明：互信息的凸性（I）互信息I(X;Y)是關(guān)于輸入分布{q(x)}和轉(zhuǎn)移概率矩陣{p(y|x)}的函數(shù)互信息的凸性（II）{q1(x)}ZX{p(y|x)}{q2(x)}Y{q

(x)}互信息的凸性（III）{q(x)}ZX{p2(y|x)}Y{p1(y|x)}{p(y|x)}=0>=0授課小結(jié)隨機變量間的平均互信息互信息的基本性質(zhì)相對熵關(guān)于疑義度的Fano不等式馬爾科夫鏈數(shù)據(jù)處理定理互信息的凸性作業(yè)復習授課內(nèi)容預習2.2至2.4節(jié)獨立完成習題（每章交一次）2.20連續(xù)隨機變量的概率密度連續(xù)隨機變量的離散化連續(xù)隨機變量的互信息（I）連續(xù)隨機變量的互信息（II）連續(xù)隨機變量的微分熵微分熵的本質(zhì)和性質(zhì)條件微分熵與聯(lián)合微分熵及其性質(zhì)熵功率例：微分熵的極大化（I）：峰值受限微分熵的極大化（II）：功率受限熵功率不等式授課小結(jié)互信息的凸性連續(xù)隨機變量的互信息及其性質(zhì)連續(xù)隨機變量的微分熵及其性質(zhì)微分熵的最大化熵功率不等式作業(yè)復習授課內(nèi)容預習2.3節(jié)獨立完成習題（每章交一次）2.21平穩(wěn)源平穩(wěn)源的熵平穩(wěn)源的熵的性質(zhì)（I）平穩(wěn)源的熵的性質(zhì)（II）平穩(wěn)源的熵的性質(zhì)（III）平穩(wěn)源的熵的性質(zhì)（IV）熵速率（熵率）馬爾科夫源馬爾科夫源的狀態(tài)圖表示s1sKmsisjxk;pij(n)xl;pji(n)時齊既約馬爾科夫源的穩(wěn)態(tài)狀態(tài)分布馬爾科夫源的熵率例：二狀態(tài)馬爾科夫源的熵率sisj

1-

1-授課小結(jié)平穩(wěn)源的平均符號熵、條件熵平穩(wěn)源的熵的性質(zhì)平穩(wěn)源的熵率馬爾科夫源及其熵率作業(yè)復習授課內(nèi)容預習3.1節(jié)獨立完成習題（每章交一次，下次課交作業(yè)）2.232.252.26（選做）第三章離散無記憶信源（DMS）的無損編碼DMS的編碼信源編碼無損編碼有損編碼（限失真編碼）絕對無差錯編碼漸進無差錯編碼目標：在代價最小的意義上來最有效地表達一個信源。包括量化、壓縮、映射、變換、自然語言翻譯等許多具體和抽象的過程。DMS編解碼系統(tǒng)概念框圖DMSuLC(uL)xN無擾信道xND(xN)uL信宿^絕對無差錯等長編碼DMS編碼符號集即編碼速率漸進無差錯等長編碼AEP性質(zhì)（I）AEP性質(zhì)（II）AEP性質(zhì)（III）由契比雪夫不等式可得給定，當L充分大時故典型列集合典型列性質(zhì)（1）：當L足夠大時，典型列性質(zhì)典型列性質(zhì)（2）：典型列性質(zhì)（3）：證明：DMS編碼定理DMS編碼定理的證明DMS的不等長編碼

消息集概率分布碼長碼字不等長碼的例子1110011111100.125a41100110010.125a31001100.25a200000.5a1碼D碼C碼B碼A出現(xiàn)概率信源消息不等長碼的基本要求唯一可譯性即時可譯性唯一可譯性非奇異性碼擴展定義：碼的任意擴展都是非奇異的，則稱碼是唯一可譯的。唯一可譯性的Sardinas&Petterson判據(jù)后綴分解后綴分解示例S0=CS1S2S3S4S5

0

10

12

21

112

1122

2102121221220121221Sardinas&Petterson判據(jù)一個碼是唯一可譯碼的充分必要條件是除S0外沒有任何一個后綴分解集中包含碼字。若S1=

，則該碼是即時可譯并且唯一可譯的。異字頭碼如果一個碼中沒有任何一個碼字是其它碼字的前綴，則稱該碼是異字頭碼，即S1=

。異字頭碼的樹形表示：所有碼字只出現(xiàn)在葉結(jié)點上0級節(jié)點（1）（2）（3）(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,3,1)(3,3,2)(3,3,3)一級節(jié)點二級節(jié)點AKraft不等式存在長度為的D元異字頭碼的充要條件為

12D

第層Kraft不等式的證明必要性：充分性：唯一可譯碼與Kraft不等式任何唯一可譯碼必然滿足Kraft不等式。證明：

r個碼字所構(gòu)成的序列的長度唯一可譯碼與異字頭碼的關(guān)系如果一個碼是唯一可譯Kraft不等式成立存在一個具有同樣長度的異字頭碼。

不等長編碼定理不等長編碼定理的證明（I）（1）不等長編碼定理的證明（II）（2）不等長編碼定理的擴展授課小結(jié)信源編碼的基本概念（編碼速率等）AEP性質(zhì)DMS等長編碼定理不等長編碼的概念唯一可譯性與Kraft不等式DMS不等長編碼定理作業(yè)復習授課內(nèi)容預習3.3節(jié)獨立完成習題（每章交一次，下次課交第二章作業(yè)）3.13.2（選做）3.33.4最佳不等長編碼（Huffman編碼）最佳不等長碼：給定信源分布，在平均碼長最 短的意義上最佳二元最佳碼：給定信源分布，其最佳二元編碼必然滿足：1）其出現(xiàn)概率越小的消息所對應的碼長越長；2）出現(xiàn)概率最小的兩個消息所對應的碼長相等，且其碼字最后一位不同最佳不等長編碼（Huffman編碼）

1）最佳不等長編碼（Huffman編碼）

2）最佳不等長編碼（Huffman編碼）

3）輔助源可遞歸編碼原理對輔助源U’的最佳編碼也是對原始源的最佳編碼。Huffman編碼(1)(0)0.60.200.190.180.170.150.100.0070.003a1a2a3a4a5a6a7a8(11)(10)(011)(010)(001)(0001)(00001)(00000)0.26(1)(0)(1)(0)0.01(1)(0)0.110.35(1)(0)1.00.39(1)(0)(1)(0)

D元Huffman編碼的虛擬消息合并0.200.190.180.170.150.100.0070.0030.00.0a1a2a3a4a5a6a7a8a9a10(1)(2)(3)(00)(01)(02)(030)(031)(3)0.01(0)(1)(2)(0)(1)(2)(3)(0)(1)(2)(3)0.431.0思考題：如何進一步增加編碼效率？授課小結(jié)唯一可譯性與Kraft不等式DMS不等長編碼定理最優(yōu)不等長編碼（Huffman編碼）作業(yè)復習授課內(nèi)容預習3.3節(jié)獨立完成習題（每章交一次）3.63.73.93.103.12Shannon編碼Shannon編碼的異字頭性Shannon編碼的效率與Huffman碼相比，Shannon碼漸進收斂性能較差，但具有競爭最優(yōu)性Fano編碼概率和對分法Fano編碼的效率(1,6)(1,2)(3,6)(4,6)(5,6)a1:00a2:01a3:10a4:110a5:1110a6:1111Shannon-Fano-Elias編碼12x

mF(x)F(x)1.0F(x-1)F(x-1)F(x-2)S-F-E編碼的效率000111140.11110.93751.00.1254001110140.11010.81250.8750.125311020.100.50.750.520100130.0010.1250.250.251Huffman碼碼字的二進表示x算術(shù)編碼熵編碼的效率熵編碼的概率排序序貫編碼基本思想：S-F-E編碼的直接推廣（從單個符號到n長序列）關(guān)鍵之處：累積概率和的快速有效的迭代算法算術(shù)編碼的基本算法（I）算術(shù)編碼的基本算法（II）T3xnT2T101通用信源編碼適用于具有任何統(tǒng)計特性的信源的有效編碼方法Shannon編碼在不能準確獲得信源分布時的性能惡化Z-L編碼序列的相異分解1011010100010…{(000,1),(000,0),(011,1),(010,1),(100,0),(010,0),(001,0)…}平穩(wěn)信源的編碼馬爾科夫源的編碼馬爾科夫源的編碼示例（I）ACDB1/0.11/0.50/0.51/0.51/0.90/0.90/0.50/0.1馬爾科夫源的編碼示例（II）對上述馬爾科夫源輸出的單符號序列進行二元編碼，則：任何狀態(tài)下均至少需要1比特來標記該輸出符號，因此平均編碼碼長。馬爾科夫源的編碼示例（III）對上述馬爾科夫源輸出的二符號序列進行二元編碼，則：ACDB01/0.0901/0.0510/0.0900/0.8100/0.4511/0.2510/0.2501/0.2511/0.8100/0.2510/0.0500/0.0511/0.0510/0.0511/0.4501/0.05馬爾科夫源的編碼示例（IV）消息ABCD000(0.81)0(0.45)10(0.25)111(0.05)0110(0.09)111(0.05)110(0.25)110(0.05)10110(0.05)110(0.25)111(0.05)10(0.09)11111(0.05)10(0.25)0(0.45)0(0.81)平均碼長1.291.851.851.29授課小結(jié)Shannon編碼Fano編碼S-F-E編碼算術(shù)編碼通用信源編碼平穩(wěn)源編碼馬爾科夫信源編碼作業(yè)復習授課內(nèi)容預習第四章獨立完成習題（下禮拜一交作業(yè)）3.143.153.16第四章信道、信道容量及

信道編碼定理引言通信的數(shù)學理論：功率與帶寬等通信資源的效用極限隨機編碼、聯(lián)合（典型列）譯碼、注水法則、特征波束賦型等重要思想方法具體通信體制（OFDM/MIMO）的理論基礎(chǔ)信道及其分類物理信道：噪聲信道、干擾信道、衰落信道、存儲信道…按輸入/輸出信號在幅度和時間上取值的連續(xù)性：幅度離散，時間離散信道；幅度連續(xù)，時間離散信道；幅度連續(xù)，時間連續(xù)信道；幅度離散，時間連續(xù)信道。按輸入/輸出之間的記憶性有記憶信道無記憶信道按其輸入/輸出信號的關(guān)系的確定性：確定信道隨機信道信道的抽象模型信道輸入量X（隨機過程）輸出量Y（隨機過程）輸入/輸出統(tǒng)計關(guān)系離散無記憶信道平穩(wěn)信道信道編碼W信道{P(yn/xn)}xn信道編碼ynW^記為：信道（互信息）容量平均每次利用信道，在輸入和輸出符號之間所能相互提供的互信息的最大值的極限離散無記憶信道（DMC）容量（I）對于離散無記憶信道（DMC）其中等號在輸入為獨立隨機序列時達到。[證明]

等號在輸出獨立也即輸入獨立時達到。離散無記憶信道（DMC）容量（II）因此，對DMC從而DMC容量的例子——無噪信道XYx1x2xMx3y1y2y3yM比特DMC容量的例子——無損信道比特XYx1x2xMB1B2BMDMC容量的例子——確定信道比特Yx1,1x1,2x1,n1x2,1x2,2x2,n2y1y2Xxm,1xm,2ymxm,nmDMC容量的例子——無用信道0101p1-pp1-pXYDMC容量的例子——二進制對稱信道（BSC）XY01011-p1-ppp當輸入取等概分布時，輸出Y也為等概分布，所以等號可以成立，即C=1-H(p).DMC容量的例子——二進制除刪信道（BEC）XY當輸入為等概分布時，等號成立.01011-p1-p

ppq1-q

BSC與BEC的容量比較和啟示pCBSC(p)CBEC(p)1C10.50授課小結(jié)信道模型離散無記憶信道容量典型信道容量的計算作業(yè)復習授課內(nèi)容預習4.2.4，4.3獨立完成習題（每章交一次）4.1（a）,（d）4.3離散無記憶信道的容量定理（I）s.t.:OP:離散無記憶信道的容量定理（II）離散無記憶信道的容量定理（III）證明：離散無記憶信道的容量定理（IV）CiCjji0K-1對稱離散無記憶信道（I）若P中每一行都是第一行的一個置換，則該信道關(guān)于輸入對稱若P中每一列都是第一列的一個置換，則該信道關(guān)于輸出對稱對稱離散無記憶信道（II）若一個信道既關(guān)于輸入對稱，又關(guān)于輸出對稱，即P中每一行都是第一行的一個置換，每一列都是第一列的一個置換，則該信道是對稱的對一個信道的轉(zhuǎn)移概率矩陣P按列劃分，得到若干子信道，若劃分出的所有子信道均是對稱的，則稱該信道是準對稱的0120.80.10.10.8010.10.1準對稱離散無記憶信道的容量定理達到準對稱離散無記憶信道容量的輸入分布為均勻分布。證：故滿足KKT條件。具有不同對稱性的信道的容量

若信道關(guān)于輸入對稱，則：若信道同時也關(guān)于輸出對稱（即信道對稱），則：若信道只關(guān)于輸入對稱，則：K元對稱信道的容量012K–1012K–1二進制除刪信道（BEC）0E11–p–q01qq1–p–qqqQ0=Q1=0.5模K加法信道+modKYXZY=X+ZmodKp(z)為任意分布

所以由概率轉(zhuǎn)移矩陣可知是對稱信道轉(zhuǎn)移概率矩陣可逆的信道的容量計算（I）令則即亦即再由得若P可逆則可解出唯一的

.進一步可得轉(zhuǎn)移概率矩陣可逆的信道的容量計算（II）進一步，再由求出{Qk}。討論：若存在某個Qk<0，則原假設前提不滿足，必須嘗試令其中某個符號不發(fā)送（不一定是符號k），再用上述過程重新計算。例子p1-p10101XY信道的組合{p1(j/k)}X1Y1{p2(j’/k’)}X2Y2{p1(j/k)}X1Y1{p2(j’/k’)}X2Y2{p1(j/k)}X1Y1{p2(j’/k’)}X2Y2平行信道（積信道）開關(guān)信道（和信道）級聯(lián)信道平行信道（積信道）{p1(j/k)}X1Y1{p2(j’/k’)}X2Y2等號在各子信道分別獨立用最佳分布發(fā)送時成立。開關(guān)信道（和信道）{p1(j/k)}X1Y1{p2(j’/k’)}X2Y2PAPBXY級聯(lián)信道{p1(j/k)}X{p2(j’/k’)}YZ授課小結(jié)離散無記憶信道容量定理對稱和準對稱信道準對稱信道容量定理轉(zhuǎn)移概率矩陣可逆的信道的容量計算信道的組合作業(yè)復習授課內(nèi)容預習4.4節(jié)獨立完成習題（每章交一次）4.24.4（選作）4.9離散無記憶信道的編碼信道編碼Xn(.)信道{p(y|x)}信道譯碼g(.)WxnynW^？離散無記憶信道的編碼可能接收到2nH(Y|X)個典型序列

Y

nxMnx2nx1n

X

n12…M

M離散無記憶信道編碼的基本定義（I）離散無記憶信道編碼的基本定義（II）發(fā)送第i個消息所發(fā)生的錯誤概率（M，n）碼的最大錯誤概率定義為（M，n）碼的平均錯誤概率定義為聯(lián)合典型列聯(lián)合典型列的性質(zhì)（I）聯(lián)合典型列的性質(zhì)（II）聯(lián)合典型列的性質(zhì)（III）

Y

nxn

X

n可能接收到2nH(Y|X)個典型序列隨機選擇yn,約有2-nI(X;Y)的概率與xn構(gòu)成聯(lián)合典型離散無記憶信道編碼定理離散無記憶信道編碼定理的證明思路漸近無差錯準則所謂可靠通信是指隨著碼長增大，錯誤概率可以任意小，但并非為零。信道上不是僅傳輸一個符號，而是傳輸一串很長符號序列。由于多次使用信道，從而可以利用大數(shù)定律獲得隨機編碼的統(tǒng)計性能。隨機編碼:計算在一類隨機選擇的碼書上的平均錯誤概率。因此至少存在一個碼書（即一個編碼），它的錯誤概率和在碼書集合上計算的平均錯誤概率一樣好。聯(lián)合（典型列）譯碼采用聯(lián)合典型的準則進行譯碼，并且這樣的譯碼準則是統(tǒng)計最優(yōu)的離散無記憶信道編碼定理的證明（I）離散無記憶信道編碼定理的證明（II）使用所有碼書發(fā)送消息w所引起的平均差錯概率離散無記憶信道編碼定理的證明（III）離散無記憶信道編碼定理的證明（IV）離散無記憶信道編碼定理的證明（V）離散無記憶信道編碼逆定理信源信道分離編碼與聯(lián)合編碼信源、信道分離編碼信源、信道聯(lián)合編碼信源信道聯(lián)合編碼定理的證明（I）證明：信源信道聯(lián)合編碼定理的證明（II）證明：信源信道分離編碼與聯(lián)合編碼只要H<C,總可以找到可行的信源信道聯(lián)合編碼；也可以分別構(gòu)造最優(yōu)的信源編碼和信道編碼，使信息傳輸可達；信源信道聯(lián)合編碼不能使得可行速率極限增加，但可以簡化編碼授課小結(jié)離散無記憶信道編碼的基本概念編碼定理及其證明思路離散無記憶信道編碼逆定理信源信道分離編碼與聯(lián)合編碼作業(yè)復習授課內(nèi)容預習4.5節(jié)獨立完成習題（每章交一次）4.12時間離散的加性高斯信道+YiXi時間離散的加性高斯信道的幅度離散化+YiXi>0<

Vi加性高斯信道的容量當輸入X為高斯分布時等號成立。高斯信道編碼定理高斯信道編碼定理之逆高斯平行信道+Y2X2+Y1X1Z1+YkXkZ2Zk

，

高斯平行信道注水法則N1N2N3N4N5N6P1P2P4P5帶限（模擬）高斯信道的容量連續(xù)信號的離散化模擬高斯信道的離散化等效平行信道+YnXnZn+Y2X2Z2+Y1X1Z1......模擬高斯信道的容量Shannon帶限信道容量定理的重要啟示授課小結(jié)加性高斯信道容量加性高斯信道的編碼定理及其證明示意平行高斯信道的容量（注水法則）帶限（模擬）高斯信道的容量及其重要意義作業(yè)復習授課內(nèi)容預習第五章獨立完成習題（每章交一次，下禮拜一交）4.13（選做）4.14第五章率失真信源編碼引言信源的無損表達：R>=H(U)信源的有損表達：R<

H(U)實數(shù)的整數(shù)化表示有限精度量化/有限電平量化/矢量量化語音圖像壓縮抽樣統(tǒng)計示例：最小化量化誤差的矢量量化12MLloyd算法Voronoi區(qū)域率失真編碼的定義12M

失真度量（函數(shù)）失真度量（函數(shù)）的重要例子失真的規(guī)范化（I）失真的規(guī)范化（II）失真的規(guī)范化（III）：例子xxabc

275

438^xxabc

053

105^零速率編碼可達到的最小平均失真率失真編碼的定義可達率失真對率失真區(qū)域率失真函數(shù)R(D)與失真率函數(shù)D(R)率失真編碼定理簡單信源的率失真函數(shù)——

Hamming失真度量下的貝努利信源（I）簡單信源的率失真函數(shù)——

Hamming失真度量下的貝努利信源（II）隨機差錯關(guān)于恢復點對稱簡單信源的率失真函數(shù)——

Hamming失真度量下的貝努利信源（III）0101簡單信源的率失真函數(shù)——

Hamming失真度量下的貝努利信源（IV）00.51p=0.5簡單信源的率失真函數(shù)——

平方誤差失真度量下的高斯信源（I）簡單信源的率失真函數(shù)——

平方誤差失真度量下的高斯信源（II）簡單信源的率失真函數(shù)——

平方誤差失真度量下的高斯信源（III）+簡單信源的率失真函數(shù)——

平方誤差失真度量下的高斯信源（IV）012簡單信源的率失真函數(shù)——

平方誤差失真度量下的高斯矢量信源（I）簡單信源的率失真函數(shù)——

平方誤差失真度量下的高斯矢量信源（II）簡單信源的率失真函數(shù)——

平方誤差失真度量下的高斯矢量信源（III）簡單信源的率失真函數(shù)——

平方誤差失真度量下的高斯矢量信源（IV）逆注水法則授課小結(jié)率失真編碼的應用背景率失真編碼的定義失真度量及其基本屬性率失真區(qū)域率失真函數(shù)與率失真編碼定理簡單信源的率失真函數(shù)作業(yè)復習授課內(nèi)容預習率失真函數(shù)的性質(zhì)5.3節(jié)作業(yè)（每章交一次）率失真函數(shù)的性質(zhì)R(D)的支撐集(Dmin,Dmax)12435R(D)的支撐集(Dmin,Dmax)貝努利信源R(D)函數(shù)的支撐集(Dmin,Dmax)高斯信源R(D)函數(shù)的支撐集(Dmin,Dmax)R(D)函數(shù)的下凸性證明：R(D)函數(shù)的單調(diào)遞減性R(D)函數(shù)的單調(diào)遞減性0DmaxH(X)離散信源0Dmax連續(xù)信源利用信源的對稱性計算率失真函數(shù)利用信源的對稱性計算率失真函數(shù)源的置換對稱性失真度量矩陣的置換對稱性利用信源的對稱性計算率失真函數(shù)利用信源的對稱性計算率失真函數(shù)例子信道編碼與限失真信源編碼的對偶授課小結(jié)率失真函數(shù)的性質(zhì)利用信源的對稱性計算率失真函數(shù)信道編碼與限失真信源編碼的對偶作業(yè)復習授課內(nèi)容作業(yè)（本章作業(yè)不交）5.25.35.8信息論與編碼第二部分基本糾錯編碼（第七章‐第九章）介紹信道編碼的基本概念與基本方式，包括分組線性碼基礎(chǔ)、循環(huán)碼與卷積碼。線性分組糾錯碼（4學時）循環(huán)碼（7學時）卷積碼（6學時）內(nèi)容提要與課時分配：第7章線性分組糾錯編碼

1、現(xiàn)代數(shù)字通信的兩個基本理論基礎(chǔ)：信息論和糾錯編碼；2、通信中信源編碼，信道編碼和數(shù)據(jù)轉(zhuǎn)換編碼常常同時使用；

本章介紹信道編碼的基本的概念、也介紹最為常用的糾錯編碼，即分組循環(huán)碼和卷積編碼。

信源編碼信道編碼數(shù)據(jù)轉(zhuǎn)換編碼數(shù)據(jù)轉(zhuǎn)換譯碼信道譯碼信源譯碼信道§7.1分組糾錯編碼的基本概念

7.1.1用于糾錯和檢錯的信道編碼

分組信道編碼器的輸入是一列長度為k的字符序列，其中字符是從信源字符表M中取值，信道編碼器把輸入消息序列映射成由n個信道字符組成的碼字，n－碼字長度，k－信息位長度，r=n–k－冗余位長度或稱校驗位長度，

碼率分組編碼器7.1.2二元對稱信道的差錯概率和差錯分布

T表示碼字中符號錯誤數(shù)目:

1-p1-ppp0011信道容量

7.1.3檢錯和糾錯

檢錯是指當碼字在信道上傳輸發(fā)生錯誤時，譯碼器能發(fā)現(xiàn)傳輸有誤；糾錯則是指譯碼器能自動糾正這個錯誤的能力。

[例7.1.3]3次重復編碼，（n=3,k=1,r=2

）

“0”→“000”，“1”→“111”檢測兩位錯誤糾正一位錯誤[例7.1.2]r=3的重復碼，即把 “0”→“0000” “1”→“1111”

糾正一位檢測兩位7.1.4自動重發(fā)請求（ARQ）編碼

在半雙工或雙工情況下，收端發(fā)現(xiàn)有誤時，可以通過反向信道去請求對方重發(fā)一次，直到正確接收到為止。這種通過檢測錯誤，發(fā)現(xiàn)錯誤而且自動請求重發(fā)的通信方式稱為ARQ方式。

1、等待式ARQ

碼字出錯概率為p，要成功傳送碼字，發(fā)方平均要發(fā)碼字次數(shù)為：

2、退N

步ARQ

3、選擇性重發(fā)ARQ

7.1.5最大似然譯碼和最小Hamming距離譯碼

發(fā)送碼字：接收序列：錯誤矢量：

二元布爾運算中，減法等同于加法二元對稱信道：

信道編碼器信道譯碼器e

r

最大后驗概率譯碼：最大似然譯碼準則：最大后驗概率譯碼＝最大似然譯碼先驗等概對于差錯概率為p的二元對稱信道來說

兩個序列和的Hamming距離為d

指這兩個序列有d位不同。7.1.6最小Hamming距離與檢錯、糾錯能力的關(guān)系

把二個長度為n

的序列和之間的Hamming距離定義為和之間對應分量取不同值的位數(shù)。

定義9.1.1

長度為n的分組碼C的最小Hamming距離d為分組碼的三個最重要參數(shù):

碼字長度n，信息位數(shù)目k，最小Hamming距離d；對于一個（n,k）分組碼來說，最小Hamming距離d與糾錯、檢錯能力有如下關(guān)系：

定理7.1.1

任何一個（n,k）分組碼，若要在任何碼字內(nèi)a.能檢測e個隨機錯誤，則要求最小Hamming距離d≥e+1。b.能糾正t個隨機錯誤，則要求d≥2t+1。c.能糾正t個隨機錯誤，同時檢測出e(≥t)個錯誤，則要求d≥t+e+1。[證明]

§7.2線性分組糾錯編碼7.2.1線性分組編碼的生成矩陣和校驗矩陣線性分組碼的基本特征是它具有“線性”的結(jié)構(gòu)，即兩個碼字的線性組合仍是碼字，對于二元碼，即兩個碼字之和仍為碼字?？梢岳脭?shù)學工具“線性空間”來研究線性分組碼，使得編碼器和譯碼器的實現(xiàn)更為簡單。

定義7.2.1

一個速率為的線性分組碼（n,k），把k

比特的消息矢量線性地映射成n比特的碼字其中線性映射：全體碼字集合稱為碼字空間，它是n維空間中的一個k維子空間。……

k個線性獨立的二元n維矢量所以消息矢量生成矩陣[例9.2.1]

G生成的（6,3）線性碼

行變換列交換系統(tǒng)生成矩陣系統(tǒng)生成矩陣生成系統(tǒng)線性碼：r=n-k

校驗位k

信息位系統(tǒng)線性碼的校驗矩陣：[例7.2.2]

例7.2.1中的（6.3）線性碼的校驗矩陣為

7.2.2對偶碼和內(nèi)積：u和v正交：n維空間中與一個k維子空間C正交的所有矢量的全體構(gòu)成一個n-k維子空間，它稱為C

的對偶空間，或稱C

的正交補，用C⊥來表示。

定義7.2.2

生成矩陣為G，校驗矩陣為H的（n,k）線性分組碼C的對偶碼C⊥是一個生成矩陣為H，校驗矩陣為G的（n,n–k）線性分組碼。

7.2.3線性分組碼的最小Hamming距離和最小Hamming重量

定義7.2.3

一個n維矢量的Hamming重量定義為該矢量中非零分量的個數(shù)，對于二元矢量也就是矢量中“1”分量的個數(shù)。因為所以線性分組碼的最小Hamming距離等于該碼中非零碼字的最小重量。

[例7.2.5]

由例9.2.3中生成矩陣所生成的線性分組碼總共有8個碼字（110100），（101010），（011001），（000000），（011110），（110011），（101101），（000111）

設若碼字重量為w，則相應w列的和為零。如果一個線性分組碼的最小Hamming距離為d，也就是說該碼的最小Hamming重量為d，則它的校驗矩陣H中任意d–1個列矢量是線性獨立的。

§7.3線性分組碼的糾錯能力

線性碼的糾錯能力是由給定n,

k條件下，最小距離d的上，下界限來表征的。下面3個定理給出關(guān)于最小距離

d的上限。定理7.3.1

（Singleton限）任何線性（n,k）碼的最小Hamming距離d滿足

定理7.3.2

（Hamming限）長度為n，能糾正t個錯誤的二元分組碼所含有碼字數(shù)M必須滿足定理7.3.3

（Plotkin限）長度為n，碼字數(shù)為M的分組碼，它的最小Hamming距離d必須滿足定理7.3.4

（Varsharmov-Gilbert下限）可以構(gòu)成一個最小距離為d的（n,k）線性分組碼，其中參數(shù)n,k,d滿足

d/2n§7.4

線性分組碼的譯碼

發(fā)送的二元碼字矢量為，從信道接收到的二元矢量為，錯誤矢量為

最大似然譯碼法則要求把譯成與之距離最近的碼字。

完全譯碼器把接收到的二元矢量譯成與它最近碼字；限定距離t譯碼器，選與最近的碼字，當時，則譯碼器就譯成；當時，譯碼器聲稱糾錯失敗。7.4.1標準陣列譯碼法

陪集首項：n維矢量中除了前面行矢量外最輕重量者二元（n,k）線性碼C，若是任意一個非碼字n維矢量，則稱集合為C的一個陪集，其中稱為陪集首項。任意二個倍集或者不相交或者重合，所以標準陣列是線性碼的完全陪集分解。

對于任何接收到的矢量，若它落在標準陣列中的第j行，則可能的錯誤形式是該行中的所有矢量，最大似然譯碼準則要求把與接收矢量最近的碼字譯為發(fā)送碼字，所以相當于在第j行中尋找最輕重量的矢量作為錯誤形式，即把該行的首項作為錯誤形式。

對于限定矩離

t

譯碼來說，不需要構(gòu)造出完整的標準陣列，只需要構(gòu)造重量不大于t

的陪集首項所對應的陪集。若接收到的矢量沒有出現(xiàn)在這個不完整陣列表中，則說明這時發(fā)生了不可糾正的錯誤。

[例7.4.1]

一個具有4個碼字，能糾錯一位的（6，2）線性碼，

C

={(000000),(010101),(101010),(111111)}000000010101101010111111000001010100101011111110000010010111101000111101000100010001101110111011001000011101100010110111010000000101111010101111100000110101001010011111…………………………………………陪集首項重量不大于1的不完全陣列表如果一個線性碼的標準陣列中的陪集首項正好是所有重量不大于t的二元矢量，該線性碼稱為完備碼。

7.4.2伴隨式譯碼

接收矢量所對應的伴隨式是一個維矢量

1、與相應的伴隨式為零矢量的充要條件是為一個碼字；

2、若則3、二個矢量出現(xiàn)在C的同一陪集中的充要條件是他們具有相同的伴隨式；所以伴隨式與陪集一一對應。如果接收到矢量為，首先計算出它的伴隨式，如果，則表示接收到的是碼字，沒有錯。如果不為0，則根據(jù)查出對應的錯誤形式。

§7.5

譯碼錯誤概率計算

誤碼字率為重量為i的陪集首項數(shù)目；誤比特率

§7.6

二元Hamming碼

定義7.6.1

長度為n=2r–1（r≥2）的二元Hamming碼是一個（n=2r–1,k=2r–1–r）線性分組碼，它的最小Hamming距離為3，能糾正全部一位錯誤。它的校驗矩陣H由全部2r–1個長度為r的非零、相異的二元列矢量組成。[例7.6.1]

對于系統(tǒng)（7.4）Hamming碼，它的校驗矩陣

§7.7

從一個已知線性分組碼來構(gòu)造一個新的線性分組碼

擴展的Hamming碼(2r,2r–1–r,4)例（16,11,4）Hamming碼Hr(2r–1,2r–1–r,3)例（15,11,3）Hr中偶重量碼字構(gòu)成的子碼(2r–1,2r–2–r,4)例（15,10,4）除刪，丟棄奇數(shù)重碼字通過加入全“1”分量碼字來增廣延長縮短（cn–1=0）

在全校驗位上鑿孔

通過增加全校驗位來擴展復習授課內(nèi)容獨立完成習題7.27.47.67.97.107.11作業(yè)：第7章線性分組糾錯編碼

第8章循環(huán)碼

為了尋找好的糾錯碼，并尋找到有效的編/譯碼算法，通常要求碼字集合除了線性以外還具有其他有用的構(gòu)造，特別是代數(shù)和幾何的結(jié)構(gòu)。循環(huán)碼是一類非常重要的線性碼，它的碼字具有循環(huán)特性，即循環(huán)碼的碼字經(jīng)循環(huán)移位后仍然是一個碼字。由于循環(huán)碼具有更多的結(jié)構(gòu)對稱性，所以它的編/譯碼實現(xiàn)的復雜性比一般線性碼更低，并有可能把編碼的糾錯性能與結(jié)構(gòu)參數(shù)聯(lián)系起來。要深入研究循環(huán)碼的結(jié)構(gòu)和編/譯碼方法，需要有一些代數(shù)方面的知識，特別是有限域的理論?！?.1

有限域代數(shù)的基本知識

8.1.1有限域的定義定義8.1.1

域F是一個由元素組成的集合，在這個集合上定義兩種運算，加法“+”和乘法“·”。這兩種運算滿足交換律、結(jié)合律和分配律，即對于,存在唯一的加法零元素“0”，,存在唯一加法逆元，存在唯一單位元“1”，

存在唯一的乘法逆元，[例8.1.1]

最簡單的有限域是二元域：其上的加法、乘法分別就是布爾加法和布爾乘法，即

對任何質(zhì)數(shù)p，可以構(gòu)成具有p個元素的伽羅華城在GF(p)上的加法和乘法分別為模p加法和模p乘法。[例8.1.2]

GF(5)是一個有5個元素的有限域，域上加法和乘法定義為：8.1.2GF(2m)的表示與構(gòu)成多項式表示：考慮系數(shù)取自GF(2)上的（m

1）次多項式：m維二元矢量表示：GF(2m)元素間的加法和乘法運算：

（1101）

（1010）

（0111）采用普通多項式的加法和乘法，系數(shù)之間的運算是采用模2運算。為了使多項式乘法是封閉的，選是GF(2)上某個m次簡約多項式的根。

在定義乘法時，遇到了困難：定理8.1.1

如果是GF(2)上次數(shù)等于m的不可約多項式，則對GF(2)上每個次數(shù)小于m的多項式，均存在唯一的逆元：8.1.3有限域的特征和元素的階數(shù)令λ為使，成立的最小整數(shù)t，這個t稱為該有限域的特征。GF(2)的特征為2。

有限域GF(q)上每個非零元，存在最小正整數(shù)k，使得，稱k為的階數(shù)。定理8.1.3

GF(q)上任何非零元素，必有定理8.1.4

令是GF(q)中非零元，的階數(shù)為k，則q

1能被k除盡。GF(16)中非零元可能的階數(shù):1,3,5,15GF(256)中非零元可能的階數(shù):1,3,5,15,17,51,85,255定義8.1.2

如果GF(q)的一個元素

的階數(shù)為q

1，則

被稱為是本原元素?？勺C明每個有限域GF(q)至少有一個本原元素。因此至少存在一個本原元素

，它的逐次冪構(gòu)成GF(q)的全部非零元，即[例8.1.3]

令是GF(2)上既約多項式的根，的逐次冪為：令是GF(2)上既約多項式的根，的逐次冪列為：定義8.1.3

GF(2)上一個m次多項，如果它的所有根均是GF(2m)中的本原元，則稱為是m次本原多項式。容易驗證例8.1.3中均是GF(24)的本原元，而是本原多項式。

1.可以證明本原多項式一定是簡約的，但簡約多項式不一定是本原的。2.GF(2m)中每個非零元的階次是2m-1的因子，所以滿足GF(2m)中所有元素是方程的根。8.1.4最小多項式設為GF(2m)中任一元素，m(x)是GF(2)上使的最低次多項式，則稱為的最小多項式。最小多項式必定是既約的。在特征為p的有限域GF(pm)中，若是系數(shù)在GF(p)上的多項式的根，則也是的根。若GF(2m)中本原元是本原多項式的根，則均是的根，它們都是本原元素。如果的最小多項式是m次的，則的共軛系是，所以的m次最小多項式可寫成：在特征為2的GF(2m)中，具有相同的最小多項式，這些元素構(gòu)成共軛系。有限域的元素可以分解成若干個共軛系?！?.2

循環(huán)碼定義與碼字的多項式表示

循環(huán)移位定義8.2.1

一個（n,k）線性碼C

，若它的每個碼字矢量的循環(huán)移位也是該碼的碼字，則我們稱C

為循環(huán)碼。[例8.2.1]

一個由4個碼字構(gòu)成的，最小重量為3的（6，2）循環(huán)碼

用多項式表示碼字矢量因為定理8.2.1

循環(huán)碼C中次數(shù)最低的非零碼字多項式是唯一的。

[證明]令是碼C

中一個次數(shù)最低的非零碼字多項式。若不是唯一的，則必然存在另一個次數(shù)為r的碼字多項式,由于C是線性的，所以這與假設是次數(shù)最低非零碼字多項式相矛盾。

定理8.2.2

令是（n,k）循環(huán)碼C中最低次數(shù)非零碼多項式，則常數(shù)項。

[證明]若所以與假設矛盾。定理8.2.3

令是（n,k）循環(huán)碼C中次數(shù)最低的非零碼字多項式，則任何一個次數(shù)不大于n–1的二元多項式，當且僅當它是g(x)倍式時，才可成為一個碼字多項式。[證明]

充分性：令是次數(shù)不大于n–1的二元多項式，且是g(x)的倍式，

上式中的被加項均是碼字多項式，所以是也一個碼字多項式；必要性：令是碼C

中一個碼字多項式，用g(x)除得到

b(x)次數(shù)小于g(x)次數(shù)；由充分性，a(x)g(x)

是一個碼字多項式，故b(x)是次數(shù)小于r的碼字多相式，于是導致矛盾?？偨Y(jié)上面3條定理得：定理8.2.4

在一個二元（n,k）循環(huán)碼中，存在唯一的次數(shù)為n–k的碼字多項式，使得每個碼字多項式都是的倍式，反之每個次數(shù)不大于n–1而且為倍式的多項式均對應于一個碼字多項式。

所有次數(shù)不大于n–1，而且是g(x)倍式的多項式是由一切形如多項式與g(x)相乘的結(jié)果，總共有2n–r個。故2n–r應該等于2k

，即。稱g(x)為這個（n,k）循環(huán)碼的生成多項式，u(x)為消息多項式。

[例8.2.2]由生成的（6.2）循環(huán)碼的碼字

生成多項式必須滿足一些條件：

定理8.2.5

（n,k）循環(huán)碼的生成多項式g(x)是xn

+1的因子。[證明]

b(x)是g(x)連續(xù)向右移位k次后所得多項式，故b(x)是一個碼字多項式。即故于是g(x)是xn+1的因式。

定理8.2.6

若g(x)是n–k次多項式，而且是xn+1的因式，則g(x)生成一個（n,k）循環(huán)碼。

[證明]

令g(x)是xn+1的一個次數(shù)為n–k的因式，則是一個次數(shù)小于或等于（n–1）的多項式，且是g(x)的倍式。總共有2k個這樣多項式。這些多項式組成一個（n,k）線性分組碼。

下面證明這個線性分組碼是循環(huán)的：

若v(x)是該線性碼的一個碼字多項式，即是g(x)的一個倍式，則所以v(1)(x)也是g(x)的倍式。從而v(1)(x)也是的線性組合，所以v(1)(x)也是一個碼字多項式。

[例8.2.3]

多項式可分解成：由生成的（7,4）循環(huán)碼

§8.3系統(tǒng)循環(huán)碼的編碼及實現(xiàn)

8.3.1系統(tǒng)循環(huán)碼的編碼

在（n,k）系統(tǒng)循環(huán)碼中，k位消息位集中在碼字矢量的右側(cè)（最高位）。

構(gòu)成系統(tǒng)循環(huán)碼的步驟如下：1、用乘以消息多項式；2、用生成多項式除，得到余式（校驗位多項式）；3、構(gòu)成碼字多項式；[例8.3.1]

考慮由生成的（7.4）循環(huán)碼，消息多項式是，求相應的系統(tǒng)碼字多項式。

[解]

1、2、3、8.3.2多項式運算的電路實現(xiàn)

一、多項式相加

c(x)+b(x)a(x)多項式，的系數(shù)依次從高到低位輸入到模2加法器，和式的系數(shù)從高到低位依次輸出。

二、多項式相乘

DDDDbr–1+brbr–2+b2+b1+b0+a(x)a0,a1,…,akc(x)c0,c1,…,ck+rb1+b0b2+br–2+br–1+br+a(x)a0,a1,…,akc(x)c0,c1,…,ck+rDDDD多項式乘法的另一種實現(xiàn)電路

[例8.3.2]

DD+a(x)1011c(x)100111DD+a(x)1011c(x)100111三、多項式除法電路

被除式除式商式余式–g1+–g0–g2+–gr3+–gr–2++d(x)d0,…,dnDDDD+DD–gr–1gr–1在n次移位后，商多項式出現(xiàn)在輸出端，寄存器中保存的是余式。[例8.3.3]

++DDD+D+DDd(x)四、乘一個多項式后，再除一個多項式的電路–g1+–g0–g2+–gr–3+–gr–2++a(x)DDDD+D–gr–1gr–1+Dh1h0h2hr–3hr–2hr–1hr乘以多項式，再除以多項式的電路

輸入++DDD+D+D+D輸出乘以多項式，再除以的電路

DDDD++DDD+D+D+D+輸入輸出8.3.3循環(huán)碼編碼的電路實現(xiàn)