桂林電子科技大學(xué)信息論與編碼試卷

1、x1=02/31=0二、綜合題（每題10分，共60分）黑白氣象傳真圖的消息只有黑色和白色兩種，求：1）黑色出現(xiàn)的概率為0.3,白色出現(xiàn)的概率為0.7。給出這個只有兩個符號的信源X的數(shù)學(xué)模型。假設(shè)圖上黑白消息出現(xiàn)前后沒有關(guān)聯(lián)，求爛豆（畫）；2）假設(shè)黑白消息出現(xiàn)前后有關(guān)聯(lián)，其依賴關(guān)系為：尸伯/白）=尸（黑f白）=0.1，F(xiàn)伯/黑）=0.2，F(xiàn)（黑/黑）=0氣求其爛巴（瓷）；曼碼，計算其平均碼長和編碼效率。二元對稱信道如圖。心=11）若，求丹徑）和徑2）求該信道的信道容量和最佳輸入分布。623JI2并設(shè)，試分別按最小錯誤概率4設(shè)有一離散信道，其信道傳遞矩陣為丘電2準(zhǔn)則與最大似然譯碼準(zhǔn)則確定譯碼規(guī)則，

2、并計算相應(yīng)的平均錯誤概率。100001110100010000100010000100015.已知一（8,5）線性分組碼的生成矩陣為L0000Iin求：1）輸入為全00011和10100時該碼的碼字；2）最小碼距。6設(shè)某一信號的信息傳輸率為5.6kbit/s,在帶寬為4kHz的高斯信道中傳輸，噪聲功率譜N0=5X106mw/Hz。試求：（1）無差錯傳輸需要的最小輸入功率是多少？（2）此時輸入信號的最大連續(xù)熵是多少？寫出對應(yīng)的輸入概率密度函數(shù)的形式。一、概念簡答題（每題5分，共40分）丹=-工尹（X）logF（旳）1答：平均自信息為表示信源的平均不確定度，也表示平均每個信源消息所提供的信息量。平

3、均互信息E詩孰砂應(yīng)瓷乎表示從Y獲得的關(guān)于每個X的平均信息量，也表示發(fā)X前后Y的平均不確定性減少的量，還表示通信前后整個系統(tǒng)不確定性減少的量。答：最大離散熵定理為：離散無記憶信源，等概率分布時熵最大。最大熵值為。答：信息傳輸率R指信道中平均每個符號所能傳送的信息量。信道容量是一個信道所能達(dá)到的最大信息傳輸率。信息傳輸率達(dá)到信道容量時所對應(yīng)的輸入概率分布稱為最佳輸入概率分布。平均互信息是信源概率分布的Q型凸函數(shù)，是信道傳遞概率的U型凸函數(shù)。答：通信系統(tǒng)模型如下：數(shù)據(jù)處理定理為：串聯(lián)信道的輸入輸出X、YZ組成一個馬爾可夫鏈，且有皿ZWZ。說明經(jīng)數(shù)據(jù)處理后，一般只會增加信息的損失。q=険務(wù)昭溫1+5.

4、答：香農(nóng)公式為bit/s，它是高斯加性白噪聲信道在單位時間內(nèi)的101g由6.答：只要，當(dāng)N足夠長時，一定存在一種無失真編碼。信道容量，其值取決于信噪比和帶寬。瓦示屈/曰而則q=50001og2(1+1000)=49836bills7.答：當(dāng)RVC時，只要碼長足夠長，一定能找到一種編碼方法和譯碼規(guī)則，使譯碼錯誤概率無窮小。8.答：1）保真度準(zhǔn)則為：平均失真度不大于允許的失真度。2）因?yàn)槭д婢仃囍忻啃卸加幸粋€0，所以有%”而加噸1一嘰嚨二、綜合題（每題10分，共60分）1答：1）信源模型為陽=黑冬二白0.30.7H(J0=log2=0.881沬/符號2）由尸他）=工尸（勺）尸洌）,“12）+尸（）

5、=1豆2理）=-工工戸）尸他）1。&戸叭仏）=0-5533拭打符萬2.答：1）HX)=0.8113加打符號7(;7)=0.0616如打符號2）c=0082符號，最佳輸入概率分布為等概率分布。3.答：1）二元碼的碼字依序?yàn)椋?0，11，010，011，1010，1011，1000，1001。平均碼長泅符號，編碼效率2）三元碼的碼字依序?yàn)椋?，00，02，20，21，22，010，011。平均碼長厶F汕符號，編碼效率甘0期4答：1）最小似然譯碼準(zhǔn)則下，有2）最大錯誤概率準(zhǔn)則下，有答：1）輸入為00011時，碼字為00011110；輸入為10100時，碼字為10100101。aQtr3對應(yīng)的輸入概率

6、密度函數(shù)為0.206x10_3信息論習(xí)題集一、名詞解釋（每詞2分）（25道）1、“本體論”的信息（P3）2、“認(rèn)識論”信息（P3）3、離散信源（11）4、自信息量（12）5、離散平穩(wěn)無記憶信源（49）6、馬爾可夫信源（58）7、信源冗余度（66）8、連續(xù)信源（68）9、信道容量（95）10、強(qiáng)對稱信道（99）11、對稱信道（101-102）12、多符號離散信道（109）13、連續(xù)信道（124）14、平均失真度（136）15、實(shí)驗(yàn)信道（138）16、率失真函數(shù)（139）17、信息價值率（163）18、游程序列（181）19、游程變換（181）20、L-D編碼（184）、21、冗余變換（184）2

7、2、BSC信道（189）23、碼的最小距離（193）24、線性分組碼（195）25、循環(huán)碼（213）二、填空（每空1分）（100道）1、在認(rèn)識論層次上研究信息的時候，必須同時考慮到形式、含義和效用三個方面的因素。2、1948年，美國數(shù)學(xué)家香農(nóng)發(fā)表了題為“通信的數(shù)學(xué)理論”的長篇論文，從而創(chuàng)立了信息論。3、按照信息的性質(zhì)，可以把信息分成語法信息、語義信息和語用信息。4、按照信息的地位，可以把信息分成客觀信息和主觀信息。5、人們研究信息論的目的是為了高效、可靠、安全地交換和利用各種各樣的信息。6、信息的可度量性是建立信息論的基礎(chǔ)。7、統(tǒng)計度量是信息度量最常用的方法。8、是香農(nóng)信息論最基本最重要的概念

8、。9、事物的不確定度是用時間統(tǒng)計發(fā)生概率的對數(shù)來描述的。10、單符號離散信源一般用隨機(jī)變量描述，而多符號離散信源一般用隨機(jī)矢量描述。11、一個隨機(jī)事件發(fā)生某一結(jié)果后所帶來的信息量稱為自信息量，定義為其發(fā)生概率對數(shù)的負(fù)值。12、自信息量的單位一般有比特、奈特和哈特。13、必然事件的自信息是。14、不可能事件的自信息量是_o15、兩個相互獨(dú)立的隨機(jī)變量的聯(lián)合自信息量等于兩個自信息量之和。16、數(shù)據(jù)處理定理：當(dāng)消息經(jīng)過多級處理后，隨著處理器數(shù)目的增多，輸入消息與輸出消息之間的平均互信息量趨于變小。17、離散平穩(wěn)無記憶信源X的N次擴(kuò)展信源的熵等于離散信源X的熵的4倍。H二limH（X/XXX）18、離

9、散平穩(wěn)有記憶信源的極限熵，gNT8N12N-1。19、20、21、22、對于n元m階馬爾可夫信源，其狀態(tài)空間共有-a個不同的狀態(tài)。一維連續(xù)隨即變量X在a,b區(qū)間內(nèi)均勻分布時，其信源熵為-log/ba)屮。屮ePc對于限峰值功率的N維連續(xù)信源，當(dāng)概率密度均勻分布時連續(xù)信源熵具有最大值。平均功率為P的高斯分布的連續(xù)信源，其信源熵，H(X)=223、對于限平均功率的一維連續(xù)信源，當(dāng)概率密度信斯分布時，信源熵有最大值。24、對于均值為0，平均功率受限的連續(xù)信源，信源的冗余度決定于平均功率的限定值P和信源的熵功率P之比。25、若一離散無記憶信源的信源熵H(X)等于2.5，對信源進(jìn)行等長的無失真二進(jìn)制編碼

10、，則編碼長度至少為。Lm-ki126、m元長度為k.,i=1，2,n的異前置碼存在的充要條件是：i=1。i27、若把擲骰子的結(jié)果作為一離散信源，則其信源熵為一28、同時擲兩個正常的骰子，各面呈現(xiàn)的概率都為1/6,則“3和5同時出現(xiàn)”這件事的自信息量是log218(1+2log23)o1-xp(x)=一em、029、若一維隨即變量X的取值區(qū)間是0,8,其概率密度函數(shù)為m，其中：x-0，m是X的數(shù)學(xué)期望，則X的信源熵HC(X)=log2me。30、一副充分洗亂的撲克牌(52張)，從中任意抽取1張，然后放回，若把這一過程看作離散無記憶信源，則其信源熵為log252。31、根據(jù)輸入輸出信號的特點(diǎn)，可將

11、信道分成離散信道、連續(xù)信道、半離散或半連續(xù)信道。32、信道的輸出僅與信道當(dāng)前輸入有關(guān)，而與過去輸入無關(guān)的信道稱為呂記憶信道。33、具有一一對應(yīng)關(guān)系的無噪信道的信道容量C=og2n。34、強(qiáng)對稱信道的信道容量C=log2n-Hni。35、對稱信道的信道容量C=log2m-Hn：36、對于離散無記憶信道和信源的N次擴(kuò)展，其信道容量Cn=:LNCk37、對于N個對立并聯(lián)信道，其信道容量CN=k=1:38、多用戶信道的信道容量用多維空間的一個區(qū)域的界限來表示。39、多用戶信道可以分成幾種最基本的類型：多址接入信道、廣播信道和相關(guān)信源信道。40、廣播信道是只有一個輸入端和多個輸出端的信道。41、當(dāng)信道的

12、噪聲對輸入的干擾作用表現(xiàn)為噪聲和輸入的線性疊加時，此信道稱為加性連續(xù)信道:1P2log2(1+滬42、高斯加性信道的信道容量C=N:43、信道編碼定理是一個理想編碼的存在性定理，即：信道無失真?zhèn)鬟f信息的條件是信息率小于信道容量:1/21/2044、信道矩陣L001J代表的信道的信道容量C=J。_10_100145、信道矩陣L代表的信道的信道容量C=L:46、高斯加性噪聲信道中，信道帶寬3kHz,信噪比為7,則該信道的最大信息傳輸速率Ct=-9-iHz47、對于具有歸并性能的無燥信道，達(dá)到信道容量的條件是p(y_)=1/m):10j48、信道矩陣L1代表的信道，若每分鐘可以傳遞6*105個符號，

13、則該信道的最大信息傳輸速率Ct=10kHz：49、信息率失真理論是量化、數(shù)模轉(zhuǎn)換、頻帶壓縮和錢據(jù)壓縮的理論基礎(chǔ)。50、求解率失真函數(shù)的問題，即：在給定失真度的情況下，求信息率的極小值。51、信源的消息通過信道傳輸后的誤差或失真越大，信宿收到消息后對信源存在的不確定性就_越大，獲得的信息量就越小。52、53、信源的消息通過信道傳輸后的誤差或失真越大道傳輸消息所需的信息率上越小。單符號的失真度或失真函數(shù)d(x.,i054、55、56、打)表示信源發(fā)出一個符號嚀信宿再現(xiàn)y所引起的誤差或失真。i=j1i豐joj漢明失真函數(shù)d(xi，yj)=ij平方誤差失真函數(shù)d(X-，y.)八.平均失真度定義為失真函

14、數(shù)的數(shù)學(xué)期望，即d(x.，y.)在X和Y的聯(lián)合概率空間P(XY)中的統(tǒng)i1計平均值。57、如果信源和失真度一定，則平均失真度是信道統(tǒng)計特性的函數(shù)。58、如果規(guī)定平均失真度D不能超過某一限定的值D，即：DD。我們把DD稱為保真度準(zhǔn)則。59、離散無記憶N次擴(kuò)展信源通過離散無記憶N次擴(kuò)展信道的平均失真度是單符號信源通過單符號信道的平均失真度的4倍。|p(y/x):DD;i=1,2,，n,j=1,2,，m60、試驗(yàn)信道的集合用PD來表示，則PD=/i61、信息率失真函數(shù)，簡稱為率失真函數(shù)，即：試驗(yàn)信道中的平均互信息量的旨小值。62、平均失真度的下限取0的條件是失真矩陣的每一行至少有一個零元素。63、平

15、均失真度的上限D(zhuǎn)取D：j=1，2,m中的最小值。64、率失真函數(shù)對允許的平均失真度是單調(diào)遞減和連續(xù)的。65、對于離散無記憶信源的率失真函數(shù)的最大值是log2n。66、當(dāng)失真度大于平均失真度的上限時D時，率失真函數(shù)R(D)=亠。max67、連續(xù)信源X的率失真函數(shù)R(D)=P(y/X)ePD68、69、11b2log當(dāng)Db2時，高斯信源在均方差失真度下的信息率失真函數(shù)為R(D)=22D保真度準(zhǔn)則下的信源編碼定理的條件是信源的信息率R大于率失真函數(shù)R(D)。70、某二元信源LrX1/21/2其失真矩陣D=Lar00，則該信源的Da=maxa/271、某二元信源LP(x)1/21/2其失真矩陣D=La

16、0，則該信源的D.=0-rX=0110a_P(X)|1/2習(xí)其失真矩陣D=a0min72、某二元信源按照不同的編碼目的，編碼可以分為三類：分別是信源編碼、信道編碼和安全編碼。信源編碼的目的是：提高通信的有效性。一般情況下，信源編碼可以分為離散信源編碼、連續(xù)信源編碼和相關(guān)信源編碼。連續(xù)信源或模擬信號的信源編碼的理論基礎(chǔ)是限失真信源編碼定理。logp(x)k2x673、74、75、76、77、在香農(nóng)編碼中，第i個碼字的長度k.和p(x.)之間有ii，則該信源的R(D)=1-H(D/a)nx對應(yīng)的二元序列的編碼效率為n,則三者的關(guān)系是n-0nn1。85、在實(shí)際的游程編碼過程中，對長碼一般采取截斷處理

17、的方法。86、“0”游程和“1”游程可以分別進(jìn)行哈夫曼編碼，兩個碼表中的碼字可以重復(fù)，但_c碼必須不同。87、在多符號的消息序列中，大量的重復(fù)出現(xiàn)的，只起占時作用的符號稱為丄余位。88、“冗余變換”即：將一個冗余序列轉(zhuǎn)換成一個二元序列和一個縮短了的多元序列。89、L-D編碼是一種分幀傳送冗余位序列的方法。90、L-D編碼適合于冗余位較多或較少的情況。91、信道編碼的最終目的是提高信號傳輸?shù)目煽啃浴?2、狹義的信道編碼即：檢、糾錯編碼。93、BSC信道即：無記憶二進(jìn)制對稱信道。94、n位重復(fù)碼的編碼效率是1/n。95、等重碼可以檢驗(yàn)全部的奇數(shù)位錯和部分的偶數(shù)位錯。mind(c,c)d-1min2

18、96、任意兩個碼字之間的最小漢明距離有稱為碼的最小距d.，則di=c主cminmin97、98、99、若糾錯碼的最小距離為d.，則可以糾正任意小于等于t=匚個差錯。min若檢錯碼的最小距離為di，則可以檢測出任意小于等于上個差錯。minmin線性分組碼是同時具有分組特性和線性特性的糾錯碼。100、循環(huán)碼即是采用循環(huán)移位特性界定的一類線性分組碼。三、判斷(每題1分)(50道)1、必然事件和不可能事件的自信息量都是0。錯2、自信息量是p(xi)的單調(diào)遞減函數(shù)。對3、單符號離散信源的自信息和信源熵都具有非負(fù)性。對4、單符號離散信源的自信息和信源熵都是一個確定值。錯5、單符號離散信源的聯(lián)合自信息量和條

19、件自信息量都是非負(fù)的和單調(diào)遞減的。對6、自信息量、條件自信息量和聯(lián)合自信息量之間有如下關(guān)系：I(xy)=I(x)+1(y/x)=I(y)+1(x/y)ijijijij對7、自信息量、條件自信息量和互信息量之間有如下關(guān)系：I(x;y)=I(x)I(x/y)=I(y)I(y/x)ijiijjji對8、當(dāng)隨即變量X和Y相互獨(dú)立時，條件熵等于信源熵。對9、當(dāng)隨即變量X和Y相互獨(dú)立時，I(X；Y)=H(X)。錯10、信源熵具有嚴(yán)格的下凸性。錯11、平均互信息量I(X；Y)對于信源概率分布p(x.)和條件概率分布p(y./x.)都具有凸函數(shù)性。對12、m階馬爾可夫信源和消息長度為m的有記憶信源,，其所含符

20、號的依賴關(guān)系相同。錯13、利用狀態(tài)極限概率和狀態(tài)一步轉(zhuǎn)移概率來求m階馬爾可夫信源的極限熵。對14、N維統(tǒng)計獨(dú)立均勻分布連續(xù)信源的熵是N維區(qū)域體積的對數(shù)。對15、一維高斯分布的連續(xù)信源，其信源熵只與其均值和方差有關(guān)。錯16、連續(xù)信源和離散信源的熵都具有非負(fù)性。錯17、連續(xù)信源和離散信源都具有可加性。對18、連續(xù)信源和離散信源的平均互信息都具有非負(fù)性。對19、定長編碼的效率一般小于不定長編碼的效率。對20、若對一離散信源(熵為H(X)進(jìn)行二進(jìn)制無失真編碼，設(shè)定長碼子長度為K,變長碼子平均長度為K，一般KK。錯21、信道容量C是I(X；Y)關(guān)于p(x.)的條件極大值。對22、離散無噪信道的信道容量等

21、于log2n:其中n是信源X的消息個數(shù)。錯p(y.)二23、對于準(zhǔn)對稱信道，當(dāng)丿m時，可達(dá)到信道容量C。錯24、多用戶信道的信道容量不能用一個數(shù)來代表。對25、多用戶信道的信道容量不能用一個數(shù)來代表，但信道的信息率可以用一個數(shù)來表示。錯26、高斯加性信道的信道容量只與信道的信噪有關(guān)。對27、信道無失真?zhèn)鬟f信息的條件是信息率小于信道容量。對28、最大信息傳輸速率，即：選擇某一信源的概率分布(p(x.)，使信道所能傳送的信息率的最大值。錯29、對于具有歸并性能的無燥信道，當(dāng)信源等概率分布時(p(xi)=l/n),達(dá)到信道容量。錯i30、求解率失真函數(shù)的問題，即：在給定失真度的情況下，求信息率的極小

22、值。對31、信源的消息通過信道傳輸后的誤差或失真越大，信宿收到消息后對信源存在的不確定性就越小，獲得的信息量就越小。錯32、當(dāng)p(x.)、p(y./x.)和d(x.,y.)給定后，平均失真度是一個隨即變量。錯ijiij33、率失真函數(shù)對允許的平均失真度具有上凸性。對34、率失真函數(shù)沒有最大值。錯35、率失真函數(shù)的最小值是0。對36、率失真函數(shù)的值與信源的輸入概率無關(guān)。錯37、信源編碼是提高通信有效性為目的的編碼。對38、信源編碼通常是通過壓縮信源的冗余度來實(shí)現(xiàn)的。對39、離散信源或數(shù)字信號的信源編碼的理論基礎(chǔ)是限失真信源編碼定理。錯40、一般情況下，哈夫曼編碼的效率大于香農(nóng)編碼和費(fèi)諾編碼。對4

23、1、在編m(m2)進(jìn)制的哈夫曼碼時，要考慮是否需要增加概率為0的碼字，以使平均碼長最短。對42、游程序列的熵(“0”游程序列的熵與“1”游程序列的熵的和)大于等于原二元序列的熵。錯43、在游程編碼過程中，“0”游程和“1”游程應(yīng)分別編碼，因此，它們的碼字不能重復(fù)。錯44、L-D編碼適合于冗余位較多和較少的情況，否則，不但不能壓縮碼率，反而使其擴(kuò)張。對45、狹義的信道編碼既是指：信道的檢、糾錯編碼。對46、對于BSC信道，信道編碼應(yīng)當(dāng)是一對一的編碼，因此，消息m的長度等于碼字c的長度。錯47、等重碼和奇(偶)校驗(yàn)碼都可以檢出全部的奇數(shù)位錯。對48、漢明碼是一種線性分組碼。對49、循環(huán)碼也是一種線

24、性分組碼。對50、卷積碼是一種特殊的線性分組碼。錯四、簡答(每題4分)(20道)1、信息的主要特征有哪些？(4)2、信息的重要性質(zhì)有哪些？(4)3、簡述幾種信息分類的準(zhǔn)則和方法。(5)4、信息論研究的內(nèi)容主要有哪些？(8)5、簡述自信息的性質(zhì)。(13)6、簡述信源熵的基本性質(zhì)。(23)7、簡述信源熵、條件熵、聯(lián)合熵和交互熵之間的關(guān)系。(48)8、信道的分類方法有哪些？(93-94)9、簡述一般離散信道容量的計算步驟。(107)10、簡述多用戶信道的分類。(115-116)11、簡述信道編碼定理。(128)12、簡述率失真函數(shù)的性質(zhì)。(140-145)13、簡述求解一般離散信源率失真函數(shù)的步驟。

25、(146-149)14、試比較信道容量與信息率失真函數(shù)。(164)15、簡述編碼的分累及各種編碼的目的。(168)16、簡述費(fèi)諾編碼的編碼步驟。(170)17、簡述二元哈夫曼編碼的編碼步驟。(173)18、簡述廣義的信道編碼的分類及各類編碼的作用。(188)19、簡述線性分組碼的性質(zhì)。(196)20、簡述循環(huán)碼的系統(tǒng)碼構(gòu)造過程。(221)“信息論與編碼”試題2007級碩士研究生2008年6月14日一、基本概念題(閉卷部分，每題4分，共40分。1小時內(nèi)完成并交卷)試證明n維隨機(jī)變量的共熵，不大于它們各自的熵之和。證明：即證明H(X1,X2,X)H(X.)12nii=1因?yàn)?I(X;Y)=H(X)

26、-H(X/Y),所以H(X/Y)H(X)。由共熵的定義和熵的鏈接準(zhǔn)則，有H(X,X丿=H(X1)+H(X2X1)H(Xi)+H(X2)H(X1,X2,X3)=H(X1)+H(X2,X3/X1)=H(X1)+H(X2/X1)+H(X3/X2,X1)H(X1)+H(X2)+H(X3)nnH(Xi，X2,Xn)=工H(X)/Xi_i，,Xi)工H(X訂i=1i=1證畢。請給出信源編碼器的主要任務(wù)以及對信源編碼的基本要求。解：信源編碼器的主要任務(wù)是完成輸入消息集合與輸出代碼集合之間的映射。對信源編碼有如下基本要求：選擇合適的信道基本符號，以使映射后的代碼適應(yīng)信道。例如，ASCII碼選用了16進(jìn)制數(shù)。尋

27、求一種方法，把信源發(fā)出的消息變換成相應(yīng)的代碼組。這種方法就是編碼，變換成的代碼就是碼字。編碼應(yīng)使消息集合與代碼組集合中的元素一一對應(yīng)。請給出平均碼長界定定理及其物理意義。解：平均碼長界定定理：若一個離散無記憶信源X,具有熵H(X)，對其編碼用D種基本符號，則總可以找到一種無失真信源編碼，構(gòu)成單義可譯碼，使其平均碼長滿足TOC o 1-5 h z HYPERLINK l bookmark89 H(X)廠H(X)b0(i=1,2,-r;j=1,2,s)ij表示信源發(fā)出符號a.而經(jīng)信道傳輸后再現(xiàn)成信道輸出符號集合中的b.所引起的誤差或失真,ij稱之為a.和b.之間的失真函數(shù)(DistortionFu

28、nction)，簡寫為d.。ijij平均失真度定義：若信源和信宿的消息集合分別為X：U，a2,ar和丫:久,b2,bj,其概率分別為P(a.)和P(b.)(i=1,2,，r;j=1,2,.,s)，信道的轉(zhuǎn)移概率為P(b./a.)，失真函數(shù)為d(a.,b.)，則稱隨機(jī)變量X和Y的聯(lián)合概率P(a.b.)對失真函數(shù)d(a.,b.)的統(tǒng)計平均值為該通信系統(tǒng)的平均失真度D。11保真度準(zhǔn)則定義：從平均的意義上來說，信道每傳送一個符號所引起的平均失真，不能超過某一給定的限定值D,即要求DD，稱這種對于失真的限制條件為保真度準(zhǔn)則。信息率失真函數(shù)定義：用給定的失真D為自變量來描述的信息傳輸速率，稱為信息率失真函

29、數(shù)，用R(D)表示。試證明(n,k)循環(huán)碼的生成多項式g(x)是xn+1的因式。證明：將生成多項式g(x)乘以xk，得xkg(x)=g(k)(x)+q(x)(xn+1)由于xkg(x)次數(shù)為n故上式中q(x)=1,而g(k)(x)是g(x)循環(huán)左移k次所得，它是g(x)的倍式，設(shè)g(k)(x)二u(x)g(x)，故有xn+1二xk+u(x)g(x)二f(x)g(x)證畢。請給出域的定義并說明集合0,1,2可否構(gòu)成域及其理由。解：域的定義：非空元素集合F,若在F中定義了加和乘兩種運(yùn)算，且滿足F關(guān)于加法構(gòu)成Abel群，其加法恒元記為0；F中非零元素全體對乘法構(gòu)成Abel群，其乘法恒元記為1；加法和

30、乘法間有如下分配律：a(b+c)=ab+ac,(b+c)a=ba+ca,則稱F是一個域?；蛘哒f，域是一個可換的、有單位元的、非零元素有逆元的環(huán)。集合0,1,2可以構(gòu)成域。對該集合中的元素定義模3加和模3乘這兩種運(yùn)算，完全符合域必須滿足的3個條件。請給出本原多項式的定義，并用一個實(shí)例來說明它的性質(zhì)。解:本原多項式的定義:若m次既約多項式p(x)除盡的xn+1的最小正整數(shù)n滿足n=2m-1，稱p(x)為本原多項式。用實(shí)例來說明本原多項式有如下性質(zhì)：本原多項式一定是既約的(因?yàn)樗怯眉燃s多項式來定義的)，但既約多項式不一定是本原的。例如：4次既約多項式x4+x+1能除盡x15+1,但除不盡任何1nn

31、-k+1,貝i(n,k)循環(huán)碼不能檢測長為l的突發(fā)錯誤所占的比值為2-(-k)。因此，循環(huán)碼檢測突發(fā)錯誤非常有效。請給出最佳自由距離卷積碼的定義并簡要說明如何獲得具有最佳自由距離的卷積碼。解：最佳自由距離卷積碼的定義：對于相同的碼率R和相同的電路復(fù)雜性(存儲單元總數(shù)m等)的各種卷積碼，使得自由距離df最大的編碼稱為最佳自由距離(OFD,OptimalFreeDistance)碼。為了得到各種OFD碼，通常采用計算機(jī)搜索的方法，即對于給定的存儲單元總數(shù)m所有可能的卷積碼編碼器，首先排除惡性卷積碼，然后對應(yīng)每一可能的卷積碼編碼器求其自由距離d，逐一比較得到自由距離df最大者即為最佳自由距離卷積碼編

32、碼器。二、綜合題(開卷部分，每題10分，共60分。閉卷部分交卷后方可參閱參考資料)1.某通信系統(tǒng)的信源輸出僅有2個符號a、b,擬采用Lempel-Ziv編碼后送信道傳輸，若某次通信需傳輸?shù)姆栃蛄袨椤癮aaaaaabbbbbbbaaaaaaaabbbbbbbabaaaaaabbbbbbbaaaaaaaaaaaaaaaaab”，請給出其Lempel-Ziv編碼結(jié)果并簡要說明該編碼的性能。解：編碼結(jié)果編碼包內(nèi)容aaaaaaabbbbbbbaaaaaaaaaaaaaaaabaaaaaaabbbbbbbabaaaaaabbbbbbbaa碼段符號數(shù)87161516如果把a(bǔ)、b看作為1、0，對編碼結(jié)果(即

33、每個編碼包)可以用4+4+1=9-bit表示，傳輸該序列用5個編碼包即45-bit，而該序列有62-bit，因此該編碼起到壓縮作用。2.若題1信源符合a、b的出現(xiàn)概率分別為0.9和0.1,擬對其采用3重擴(kuò)展后再進(jìn)行霍夫曼編碼，請給出編碼過程及結(jié)果，并求該種信源編碼的效率。解：aaa：0.729aab：0.081aba：0.081abb：0.009baa：0.081bab：0.009bba：0.009bbb：0.001x9,按照概率大小依此排列，有設(shè)aaa、aab、bbb分另U為x1x2、x1x2x3x5x4x6x7x8具體編碼過程、結(jié)果、編碼效率一略。為了在有噪信道中獲得可靠的通信，擬對題2的

34、霍夫曼編碼結(jié)果再進(jìn)行信道編碼，若霍夫曼編碼的輸出序列為aabbbaaabababbaabbbaabbbabab,試給出采用戈萊碼(23,12)編碼的第一個碼字；如果信道編碼不是采用戈萊碼而是采用縮短的BCH(120,78)編碼，試給出構(gòu)造該種編碼的生成多項式的方法以及縮短的方法，分析其糾錯和檢錯能力，簡述其編碼和譯碼過程。解：(1)對戈萊碼(23,12)采用生成多項式為g(x)=x11+x10+x6+x5+x4+x2+1,即110001110101令a=1,b=0,則要編碼的序列為1100011101010011000110001010；由于戈萊碼是非本原BCH碼，其編碼規(guī)則與BCH碼相同，現(xiàn)

35、采用系統(tǒng)碼，第一個碼字的編碼過程如下：1100011101010000000000011000111010100000000000因此第一個戈萊碼碼字為11000111010100000000000,即監(jiān)督位為全0(11位)。(2)縮短的BCH(120,78)原碼為BCH(127,85),構(gòu)造該種編碼的生成多項式,可以由g(x)=LCM1(x)+02(x)+03(x)x6+021(x)對于本題，127=27,0j(x)是GF(27)上的元素ai的最小多項式，求出a、a3、a5、a7的最小多項式，將它們相乘即得到該種編碼能夠糾5個錯的生成多項式(次數(shù)為12785=42)?？s短的方法取原碼BCH(127,85)中的一個子集，其消息位的前7位均為0,編碼方法與原碼相同，只是傳輸時前7位0不要傳送。由求其生成多項式的過程已知該種編碼的原碼能夠糾5個隨機(jī)錯誤，至少能夠檢測10個隨機(jī)錯誤，由于其監(jiān)督位的個數(shù)位42，它能夠檢測42個突發(fā)錯誤并依概率檢測大于42個突發(fā)錯誤。其編碼方法上面已經(jīng)說明，可以采用系統(tǒng)碼的編碼方法，只是傳輸時前7位0不要傳送。解碼時通常先補(bǔ)上縮短的0的位數(shù)，再按照原碼的譯碼方法進(jìn)行譯碼，通常采用伴隨式譯碼方法。即：先求出接收序列的