一、概念簡答題（每題5分，共40分）

1.什么是平均自信息量與平均互信息，比較一下這兩個概念的異同？

月（X）??＞（4）1。8雙引

答：平均自信息為

表示信源的平均不確定度，也表示平均每個信源消息所提供的信息量。

平均互信息

表示從Y獲得的關于每個X的平均信息量，也表示發X前后Y的平均不確定性減少的量，還

表示通信前后整個系統不確定性減少的量。

2.簡述最大離散端定理。對于一個有m個符號的底散信源，其最大儲是多少？

答：最大離散牖定理為：離散無記憶信源，等概率分布時端最大。

最大端值為Hm-log2m

3.解釋信息傳輸率、信道容量、最佳輸入分布的概念，說明平均互信息與信源的

概率分布、信道的傳遞概率間分別是什么關系？

答：信息傳輸率R指信道中平均每個符號所能傳送的信息量。信道容量是一個信道所能達到

的最大信息傳輸率。信息傳輸率達到信道容量時所對應的輸入概率分布稱為最佳愉入概率分

布。

平均互信息是信源概率分布的C型凸函數，是信道傳遞概率的U型凸函數。

4.對于一個一般的通信系統，試給出其系統模型框圖，并結合此圖，解釋數據處

理定理。

笞：通信卜自源卜S.編曲/一恰；

數據處理定理為：串聯信道的輸入輸出X、Y、4且成一個馬爾可夫鏈，且有

I(X;Z)<J(X;Y)1(X;Z)<J(Y;Z))。說明經數據處理后，一般只會增加信息的損失。

5.寫出香農公式，并說明其物理意義。當信道帶寬為5000Hz,信噪比為30dB時

求信道容量。

C

Ci-bm-"I*

.答：香農公式為，它是高斯加性白噪聲信道在單位時

間內的信道容量，其值取決于信噪比和帶寬。

由""而F.dB(j而⑻則C;=50001og2(1+1000)-49836bit/

6.解釋無失真變長信源編碼定理。

一力⑺

.答：只要，心?一，不當N足夠長時，一定存在一種無失真編碼。

7.解釋有噪信道編碼定理。

答：當R〈C時，只要碼長足夠長，一定能找到一種編碼方法和譯碼規則，使譯碼錯誤概率

無窮小。

u1[011仁.

8.什么是保真度準則？對二元信源似““上?司，其失真矩BJ

求aX)時率失真函數的P和P?

答：1)保真度準則為：平均失真度不大于允許的失真度。

2)因為失真矩陣中每行都有一個0,所以有Dani-0,而

Dm=min{(l-a)a,a)

二、綜合題(每題10分，共60分)

L黑白氣象傳真圖的消息只有黑色和白色兩種，求:

1）黑色出現的概率為0.3,白色出現的概率為0.7。給出這個只有兩個符號的信源X的數

學模型。假設圖上黑白消息出現前后沒有關聯，求燃H（X）;

2）假設黑白消息出現前后有關聯，其依賴關系為：P白/白-09,P黑白）-01

p白/黑）=0.2,P黑/黑-0.8,求其端山（X）；

2.二元對稱信道如圖。

D川0）求H（x）和，西力

2）求該信道的信道容量和最佳輸入分布。

弓S備多與與

3.信源空間為104020101005005005005J試分別構造二元和三元霍夫

曼碼，計算其平均碼長和編碼效率。

236

4.設有一離散信道，其信道傳遞矩陣為卜62],⑸，試分別按最小錯誤概率

法則與最人似然譯碼準則跑定譯碼規則，并計算相應的平均錯誤概率。

IOOOOII1

01000100

00100010

00010001

5.已知一（8,5）線性分組碼的生成矩陣為00001111

求：1）輸入為全00011和10100時該碼的碼字;2）最小碼距。

6.設某一信號的信息傳輸率為5.6kbit/s,在帶寬為4kHz的高斯信道中傳輸，噪聲功率譜

NO=5x10-6mw/Hz。試求：

（1）無差錯傳輸需要的最小輸入功率是多少？

（2）此時輸入信號的最大連續燧是多少？寫出對應的輸入概率密度函數的形式。

概念簡答題（每題5分，共4。分）

1.

2.

3.答：信息傳輸率R指信道中平均每個符號所能傳送的信息量。信道容量是一個信道所能達到的最大信息

傳輸率。信息傳輸率達到信道容量時所對應的輸入概率分布稱為最佳輸入概率分布。

平均互信息是信源概率分布的n型凸函數，是信道傳遞概率的u型凸函數。

4.

5

6

7.答：當1^<0寸，只要碼^足夠長，一定能找到一種編碼方法和譯碼規則，使譯碼錯誤概率無窮小。

8.

二、綜合題（每題10分，共60分）

內?黑a產自

1.答：1)信源模型)”.

^)-0881bul^m

*i-12

2)由]w?i得

H式X)??￡￡「依於與⑷*29?05533

則MH

2答.])H(X)=0.8113bit/符號

l(X;Y)=0.0616bit/符號

2)C=0.082bit/符號，最佳輸入概率分布為等概率分布。

3.答：1)二元碼的碼字依序為：10,11,010,011,1010,1011,1000,1001o

平均碼長'LZ=2.6bit/符號，編碼效率7,2=0.97

2)三元碼的碼字依序為：1,00,02,20,21,22,010,011。

平均碼長1_3=1.7bit/符號，編碼效率馬=0.936

尸5)**1

/6)■今

夕6)■與

4.答：1)最小似然譯他準則下，有3

尸■玉

尸3P?巧a

尸5)F

2)最大錯誤概率準則下，有24

5.答:1）輸入為00011時，碼字為00011110;輸入為10100時,碼字為10100101。

2）=2

■?有八C—以

56xH“x1O>M（H5x]o，：4xd）.尸20。3制f

HJ■-54片〃自由度

2）在P=0.0328加卬時，最大尷

1"ooSwF

PW=f

對應的輸入概率密度函數為用206x1。"

信息論習題集

一、名詞解釋（每詞2分）（25道）

1、“本體論”的信息（P3）2、“認識論”信息（P3）3、離散信源（11）

4、自信息量（12）5、離散平稔無記憶信源（49）6、馬爾可夫信源（58）

7、信源冗余度（66）8、連續信源（68）9、信道容量（95）

10、強對稱信道（99）11、對稱信道（101-102）12.多符號離散信道（109）

13、連續信道（124）14、平均失真度（136）15、實驗信道（138）

16、率失真函數（139）17、信息價值率（163）18、游程序列（181）

19、游程變換（】81）20、LD編碼（184）、21、冗余變換（184）

22、BSC信道（189）23、碼的最小距離（193）24、線性分組碼（195）

25、循環碼（213）

二、填空（每空1分）（100道）

1、在認識論層次上研究信息的時候，必須同時考慮到形式、含義和效用三個方面的因素。

2、1948年，美國數學家香農發表了題為“通信的數學理論”號長篇論文,從而創立了信息論。

3、按照信息的性質，可可而語息分成語法信息、語義信息和語用信息。

4、按照信息的地位，可以把信息分成客觀信息和主觀信息。

5、人們研究信息論的目的是為了高效、可靠、安全地交換和利用各種各樣的信息。

6、信息的可度量性是建立信息論的基礎:

7、統計度量是信息度量最常用的方法。

8、一足杏是信息論最基本最重要的概念。

9、邛物的不確定度是用時間統計發生概率的對數來描述的。

10、單符號離散信源一般用隨機變量描述，而多符號離散信源?般用隨機矢量描述，

11、一個隨機事件發生某一結果后所帶來的信息量稱為自信息量，定文為其發生概率對數的負值。

12、自信息量的單位一般有比特、奈特和哈特。

13、必然事件的自信息是0、

14,不可能事件的自信息量是0。

15、兩個相互獨立的隨機變量的聯合自信息量等于兩個自信息量之和。

16、數據處理定理：當消息經過多級處理后，隨著處理器數FI的增多，輸入消息與輸出消息之間的平均互

信息量趨于變小。

17、離散平穩無記憶信源X的N次擴展信源的烯等于離散信源X的端的N倍

18、離散平穩有記憶信源的極凝，〃-㈣IX&X、」

19、對丁n元m階馬爾可夫信源，其狀態空間共有「亡個不同的狀態。

20、一維連續隨即變量X在［a,b］區間內均勻分布時，其信源雄為1。晨b-a)

21、平均功率為P的高斯分布R勺連續信源，其信源微H,(、

22、對于限峰值功率的N維連續信源，當概率密度均勻分布時連續信源唯具有最大值。

23、對于限平均功率的一維連續信源，當概率密度高斯分布時,信源燧有最大值。

24、對于均值為0,平均功率受限的連續信源，信源的冗余度決定于平均功率的限定值P和信源的牖功率F

條#一離散無記憶信源的信源燧H(X)等于2.5,對信源進行等長的無失真二進制編碼，則編碼長度至

少為3。

26、m元長度為kj=12…n的異前置碼存在的充要條件是：白"

27、若把擲骰子的結果作為一離散信源，則其信源嫌為1。盛。

28、同時擲兩個正常的骰干，各而呈現的概率都為1/6,則“3和5同時出現”這件事的自信息量是四

(1+2log3)<.

I《

p(x)?一，-

29、若一維隨即變量X的取值區間是［0,?］，其概率密度函數為m，其中：x20,m是

X的數學期望，則x的信源煙iHc(X)=log2me

30、一副充分洗亂的撲克牌(52張)，從中任意抽取1張，然后放回，若把這一過程看作離散無記憶信源，

則其信源炳為log252

31、根據輸入輸出信號的特點，可將信道分成離散信道、連續信道、半離散或半連續信道。

32、信道的輸出僅與信道當前輸入有關，而與過去輸入無關的信道稱為尢記憶，信道。

33、具的一一對應關系的無噪信道的信道容量C=logn.

34、強對稱信道的信道容量Ologn-Hnu

35、對稱信道的信道容量C=j駟他i。

36、對于離散無記憶信道和信源的N次擴展，其信道容量CN=NC

JT

yc

37、對于N個對立并聯信道，其信道容量Cx=9t

38、多用戶信道的信道容量用多維空間的一個區域的界限來表示。

39、多用戶信道可以分成JL種最基本的類型：子址接入信道、廣播信道和相關信源信道。

40、廣播信道是只有個輸入端和多個輸出端的信道。

41、當信道的噪聲對輸入的干擾作用表現為噪聲和輸入的線性疊加時，此信道稱為加性連續信道。

—log，I十)

42、高斯加性信道的信道容量C、2f\

43、信道編碼定理是一個理想編碼的存在性定理，即：信道無失真傳遞信息的條件是信息率小于信道容量。

1/21/20〕

的、信道矩陣I°°1)代表的信道的信道容量C=1

1O'

I0

45、信道矩陣10L代表的信道的信道容量C=!。

46、高斯加性噪聲信道中，信道帶寬3kHz，信噪比為7,則該信道的最大信息傳輸速率C=9kHz

47、對于具有歸并性能的無燥信道，達到信道容量的條件是p(/i)=l/m)

I0

48、信道矩陣[心L代表的信道，若每分鐘可以傳遞6*10$個符號，則該信道的最大信息傳輸速率C=

10kHz。

49、信息率失真理論是量化、數模轉換、頻帶壓縮和數據壓縮的理論基礎。

50、求解率失真函數的問題，即：在給定失真度的楮況卜'，求信息率的極小值。

51、信源的消息通過信道傳輸后的誤差或失真越大，信宿收到消息后對信源存在的不確定性就越大，獲

得的信息量就越小。------

52、信源的消息通過信道傳輸后的誤差或失真越大道傳輸消息所需的信息率也越小。

53、單符號的失真度或失真函數d(x,y;)表示信源發出一個符號x,信宿再現Y;所引起的誤差或失真

54、漢明失真函數da?1,)

55、平方誤差失直函蝶1善際■(駒

56、平均失真度定義為失真函數的數學期望,即d(xy)在X利Y的聯合概率空間P(XY)中的統

計平均值。------------------------

57、如果信源和失真度一定，則平均失真度是佶道統計特性的函數。

58、如果規定平均失真度D不能超過某平艮定的值D.即：D<Do我們把*D稱為保真度準則

59、離散無記憶N次擴展信源通過離散無記憶N次擴展信道的平均失真度是單符號信源通過單符號信道的

平均失真度的N倍。

60s試驗信道的集合用I力來表示，則Pp={P?，/x)：D力;i=l,2,……,m}

61、信息率失真函數，簡稱為率失真函數，即：試驗信道中的立均互信息量的最小值。

62、平均失真度的下限取0的條件是失真矩陣的一短一行至少有一個零元素。

63、率均決真劇而上限Dmx取{D:j=l,2,...,m}小的最力、值。

64、率失真函數對允許的平均失真度是單調遞減和連續的。

65、對于離散無記憶信源的率失真函數的最大值是logno

66、當失真度大于平均失真度的上限時Dmx時，率失真函數R(D)=a

Inf

57、連續信源X的率失真函數RI)='/?)€r.

IG

68、當⑷時，高斯信源在均方差失真度下的信息率失真函數為"八L2^D

69、保真度準則H的信源編碼定理的條件是信源的信息率R大于率失真函數R(D)_。

X][0I]「0「

70、某二元信源1|/2"2,其失真矩陣敗1"(flJ則該信源的Dmax=a/2

1|0]「。。

71、某二元信源[八*1|/2"2；其失真矩陣D=3則該信源的Dmin=0。

*1]0I|「0“

72、某二元信源「IX)]|/2=21其失真矩陣D：?■0」，則該信?源的R(D)-l-H(D/a)

73.按照不同的編碼目的，場碼可以分為三類：分別是信源編嗎、信道姐碼和安全編碼.

74、信源編碼的目的是：提高通信的行效性。

75、?般情況下，信源編碼可以分為離散信源編碼、連續信源編碼和相關信源編碼。

76、連續信源或模擬信號的信源編碼的理論基礎是

77、在香農編碼中，第1個碼字的長度k和p(x)之間有一lbg:p(x)Wk,<l-lbg:p(x)關系。

X1J/X.小X4耳9分孫Jr.

1/41/81/81/161/161/16”電,進行二進制費諾編

78、對信源

碼,其編碼效率為1

79、對具有8個:謔的單符號離散無記憶信源進行4進制哈夫曼編碼時，為使平均碼長最短，應增加2個

概率為。的消息。

80、對于香農編碼、費諾編碼和哈夫曼編碼，編碼方法惟一的是香農編碼。

81、對于二元序列0011100000011111001111000001111111,其相應的游程序列是23652457。

82、設無記憶二元序列中，“0”和“1”的概率分別是po和pi,則“0”游程長度”0)的概率為

VI

p|t(0l|=p0Pl

83、游程序列的燧等于原二元序列的端。

84、若“0”游程的喑天嗎編碼效率為no,"l”游程的哈夫嗎編碼效率為ni,ILnO>n;對應的二元序列的

編碼效率為n,則三者的關系是n>n>n。

&5、在實際的游程編碼過程中，對長碼?般采取截斷處理的方法。

86、“0”游程和“1”游程可以分別進行哈夫哽編碼，兩個碼表中的碼字可以重復，但C碼必須不同

87、在多符號的消息序列中，大量的重復出現的，只起占時作用的符號稱為冗余位。

88、“冗余變換”即：將一個冗余序列轉換成一個二元序列和一個縮短了的多元序列

89、L-D編碼是一種分恢傳送冗余位序列的方法。

90、L-D編碼適合于冗余位較多或較少的情況。

91、信道編碼的最終目的是提高信號傳輸的可靠性.

92、狹義的精造編碼即：裕、9憎物啪節:

93、BSC信道即：無記憶二進制對■稱信道.

94、n位,復碼的編碼效率是1/n

95、等重碼可以檢驗全部的奇數位錯和部分的偶數位錯

6、任意兩個碼字之間的最小漢明距離有稱為碼的最小距d則

97、若糾錯碼的最小距離為dmin,則可以糾正任意小于等于鼻L2J個差錯,

98、若檢錯碼的最小距離為dmin,則可以檢測出任意小于等于l=dminl個差錯。

99、線性分組碼是同時具有分組特性和線性特性的糾錯碼。

100、循環碼即是采用循環移位特性界定的,類線性分組碼。

三、判斷(每題1分)(50道)

1、必然事件和不可能事件的自信息量都是0。錯

2、自信息量是P(xi)的單調遞減函數。對

3、單符號離散信源的自信息和信源熠都具有非負性。對

4、單符號離散信源的自信息和信源端都是一個確定值。錯

5、單符號離散信源的聯合自信息量和條件自信息量都是非負的和單調遞減的。對

6、自信息量、條件自信息量和聯合自信息量之間有如卜關系：

l(xiyj)=l(xi)+I(y;lx!)=I(yj)+l(x,/y;)對

7、自信息量、知牛自信息量和互信息量之間有如下關系：

Hx;y;)=I(X!)-I(x;/yj)=l(y;)-Hy;/xj)對

8、當隨即變量X和Y相互獨立時，條件場等于信涮機對

9、當隨即變量X和Y相互獨立時，I(X;Y)=H(X)。錯

10、信源墉具有嚴格的下凸性。錯

11、平均互信息量I(X;Y)對于信源概率分布p(x)和條件概率分布p(y;/x)都具有凸函數性。對

12、m階馬爾可夫信源和消息長度為m的有記憶信源，其同造符號的依賴關系相同。錯

13、利用狀態極限概率和狀態一步轉移概率來求mP介馬爾可夫信源的極F瞬。對

14、N維統計獨立均勻分布連續佶源的端是N維區域體積的對數。對

15、-維高斯分布的連續信源，其信源端只與其均值和方差有關。錯

16、連續信源和離散信源的炳都具有非負性。錯

17、連續信源和離散信源都具有可加性。對

18、連續信源和離散信源的平均互信息都具有非負性。對

19、定長編碼的效率一般小于不定長編碼的效率。對

20、若對一離散信源(炳為H[X))進行二進制無失真編碼，設定長碼子長度為K,變長碼子平均長度為

區―■般J^>Ko錯

21：信道容量C盤I(X;Y)關于p(x)的條件極大值。對

22、離散無噪信道的信道容量等于logn,其中n是信源X的消息個數。錯

23、對于準對稱信道，當""”.時，可達到信道容量C借

24、多用戶信道的信道容量不能用一個數來代表。對

25、多用戶信道的信道容量不能用一個數來代表，但信道的信息率可以用一個數來表示。錯

26、高斯加性信道的信道容量只與信道的信噪有關。對

27、信道無失真傳遞信息的條件是信息率小于信道容量。對

28、最大信息傳輸速率，即：選擇某一信源的概率分布(p(x)X使信道所能傳送的信息率的最大值。錯

29、對于具有歸并性能的無燥信道，當信源等概率分布時(p(x)=l/n),達到信道容量。錯

30、求解率失真函數的問題，即：在給定失真度的情況下，求信息率的極小值。對

31、信源的消息通過信道傳輸后的誤差或失真越大，信宿收到消息后對信源存在的不確定性就越小，獲得

的信息量輟小。錯

32、當p(x)、pCy/x)和d：x,y;)給定后，平均失真度是一個隨即變量。錯

33、率失真函數對允許的平均失真度具有上凸性。對

弘、率失真函數沒有最大值。錯

35、率失真函數的最小值是0。對

36、率失真函數的值與信源的輸入概率無關。錯

37、信源編碼是提高通信有效性為目的的編碼。對

取信源編碼通常是通過壓縮信源的冗余度來實現的。對

39、離散信源或數字信號的信源編碼的理論基礎是限失真信源編碼定理。錯

40、一般情況下，哈夫曼編碼的效率大于香農編碼和費諾編碼。對

41、在編nXm>2)進制的哈夫曼碼時，要考慮是否需要增加概率為0的碼字，以使平均碼長最短。對

42、游程序列的廊“0”游程序列的端與“1”游程序列的懶的利大于等于原二元序列的嘏錯

43、在游程編碼過程中，“0”游程和“1”湘航分別編碼，因此它們的碼字不能重然錯

44、I庫碼適合于冗余位較多和較少的情況，否則，不但不能壓縮碼率，反而使其擴張。對

45、狹義的信道編碼既是指：信道的檢、糾錯編碼。對

46、對于BSC信道，信道編碼應當是一對一的編碼，因此，消息m的長度等于碼字c的長度。錯

47、等重碼和奇(偶)校驗碼都可以檢出全部的奇數位錯。對

伯、漢明碼是一種線性分組碼。對

49、循環碼也是一種線性分組碼。對

50、卷積碼是一種特殊的線性分組碼。錯

四、簡答(每題4分)(20道)

1、信息的主要特征有哪些？⑷

2、信息的重要性質有哪些？(4)

3、簡述幾種信息分類的準則和方法。⑸

4、信息論研究的內容主要有咖嶼？(8)

5、簡述自信息的性質。(13)

6、簡述信源烯的基本性質。(23)

7、筒述信源炳、條件燧、聯合烯和交互端之間的關系。(48)

8、信道的分類方法有哪些？(93F4)

9、簡述一般離散信道容量的計算步驟。(107)

10、簡述多用戶信道的分類。(115H16)

11、簡述信道編碼定理。(128)

12、簡述率失真函數的性質。(140-145)

13、簡述求解一般離散信源率失真函數的步驟。(146149)

14、試比較信道容量與信息率失真函數。(164)

15、簡述編碼的分累及各種編碼的目的。(168)

16、簡述費諾編碼的編碼步驟。(170)

17、簡述二元哈夫曼編碼的編碼步驟。(173)

18、簡述廣義的信道編碼的分類及各類編碼的作用。(188)

19、簡述線性分組碼的性質。(196)

20、簡述循環碼的系統碼構造過程。(221)

“信息論與編碼”試題2007級碩士研究生

2008年6月14日

一、基本概念題(閉卷部分，每題4分，共40分。1小時內完成并交卷)

1.試證明n維隨機變量的共嫡，不大于它們各自的炳之和。

證明：

■

■if明//<X,.X2.-Z〃(XJ

因為OW1(X;Y)=H(X)-H(X/Y),

所以H(X/Y)<H(X)o

由共燃的定義和燃的鏈接準則，有

H(Xi,X2)=H(Xi)+H(X2/X)<H(XI)+H(X2)

H(Xi,X2,X3)=H(Xi)+H(X2,X3/XI)

=H(Xi)+H(X2/Xi)+H(X3/X2,Xi)<H(Xi)+H(X2)+H(X3)

|.-.X|)S￡//(X.

4內..9I-II

，■If?BI

證畢。

2.請給出信源編碼器的主要任務以及對信源編碼的基本要求。解：信源編碼器的主要任務是

完成輸入消息集合與輸出代碼集合之間的映射。

對信源編碼有如下基本要求：

(1)選擇合適的信道基本符號，以使映射后的代碼適應信道。例如，ASCII碼選用

了16進制數。

(2)尋求一種方法，把信源發出的消息變換成相應的代碼組。這種方法就是編碼，變

換成的代碼就是碼字。

(3)編碼應使消息集合與代碼組集合中的元素一一對應。

3.請給出平均碼長界定定理及其物理意義。解：平均碼長界定定理：若一個離散無記憶信源

X,具有燃H(X),對其編碼用D種基本符號，則總可以找到一種無失真信源編碼，構成單

義可譯碼，使其平均碼長滿足

//(X?W(X)

----------464-----------.I

logDk喧。

平均碼長界定定理的物理意義：

編碼所追求的，是在單義可譯前提下尋求盡可能小的平均碼長。平均碼長界定定理指出，

平均碼長的界指瓦.."‘'二對于給定信源空間｛XRX)｝的離散信源，其端H(X)是確

I11JIviLEL?loflE

定的數值，如果信道基本符號也是確定的，即D也是給定的，則b也就定了。這意味著，

如果不改變信源的統計特性，減小b的潛力，到了其卜.界值也就到了極限了。因此，如果要

進?步提高編碼效率，必須對信源本身進行研究，例如改變信源本身的統計特性，對其進行

擴展。

4.請給出連續信源分別為均勻分布、高斯分布和指數分布時信源的相對熠。解：(1)均勻分

布連續信源的相對端為

/?(1>?-J/?(4)!?￥/><I

=log(b-a)

(2)高斯分布連續信源X的相對端為

p(x)ln/>(1)4/1

.

■■j.p(x)ln

I..(JT_

-『(外加百丁""?MG'V電

?InjliiG'?：r中間步驟可以省略

B?—)*

■一1?《2萬。)?—

22

I：I

■-la<2io)?-Inc

22

="IH(2X<O2)

9

(3)指數分布連續信源X的相對燃為

中間步驟可以省略

5.請給出失真函數、平均失真度、保真度準則、信息率失真函數的定義。解：失真函數定義：

對于有失真的信息傳輸系統，對應于每一對(aj,b)(n=l,2，…可=1,2,....,s),定義一個

非負實值函數

d(ai,bt)>0(i=l,2,...r;j=l,2....s)

表示信源發出符號a;而經信道傳輸后再現成信道輸出符號集合中的b,所引起的誤差或失真，

稱之為a;和b;之間的失真函數(DistortionFunction),簡寫為dy。

平均失真度定義:若‘言源和信宿的消息集合分別為X:{[ai,az,....，&}和Y:{bi,bz,-b:},

其概率分別為P3)和P(b)(i=l,2,……,可=1,2,……,s)，信道的轉移概率為P(b;/a),失真

函數為d(a,bi),則稱隨機變量X和Y的聯合概率P(ab)對失真函數d(a,b)的統計平均

/A-決H文:由伯至緯白々平+勺生育而n

保真度嬴i定義：屏均總意工上來說，信道每傳送一個符號所引起的平均失真，不能

超過某一給定的限定值D,即要求回，稱這種對于失真的限制條件為保真度準則，

信息率失真函數定義：用給定的失真D為白變量來描述的信息傳輸速率，稱為信息率

失真函數，用R(D)表示。

6.試證明(n,k)循環碼的生成多項式g(x)是父+1的因式。

證明：將生成多項式g(x)乘以X，，得

xAg(x)=gA*(x)+q(x)(x4+1)

由于x^g(x)次數為n,故上式中q(x)=l,而g(x)是g(x)循環左移k次所得，它是g(x)

的倍式，設g"(x)=u(x)g(x),故有式+1=伙4+u(x)]g(x)=f(x)g(x)

證畢。

7.請給出域的定義并說明集合｛0,1,2｝可否構成域及其理由。

解：域的定義：非空元素集合F,若在F中定義了加和乘兩種運算，且滿足

(DF關于加法構成Abel群，其加法恒元記為0;

(2)F中非零元素全體對乘法構成Abel群，其乘法恒元記為1;

(3)加法和乘法間有如下分配律：a(b+c)=ab+ac,(b+c)a=ba+ca,

則稱F是?個域。

或者說，域是一個可換的、有單位元的、非零元素有逆元的環。

集合(0,1,2｝可以構成域《對該集合中的元素定義模3加和模3乘這兩種運算，完全符

合域必須滿足的3個條件.

8.請給出本原多項式的定義，并用一個實例來說明它的性質。

解：本原多項式的定義：若m次既約多項式p(x)除盡的x*+l的最小正整數n滿足

稱p(x)為本原多項式。

用實例來說明本原多項式有如下性質：

1)本原多項式一定是既約的(因為它是用既約多項式來定義的)，但既約多項式不?定

是本原的。

例如：4次既約多項式x*+x+l能除盡x"+l,但除不盡任何1<水15的x”+1,所以X，

+X+1是本原的；但同樣是4次既約多項式x4+X3+X2+X+1,能除盡x5+l,但也能除盡

X2+l,所以x4+x3+x?+x+l是既約的但不是本原的。

2)對于給定的m,可能有不止一個m次本原多項式。

例如，對于m=5,x?+x?+1是本原多項式，x2+x2+1也是。

9.試說明(n,k)循環碼對突發錯誤的檢測能力。

解：(1)(n,k)循環碼能檢測長為n-k或更短的任何突發錯誤，包括首尾相接突發錯

誤。

(2)(n.k)循環碼對n-k+1位長的突發錯誤不能被檢出所占的概率最大是2(a-*+D。

⑶如果I>n-k+l,則(n,k)循環碼不能檢測長為1的突發錯誤所占的比值為2~(n-

k)o

因此，循環碼檢測突發錯誤非常有效。

10.請給出最佳自由距離卷積碼的定義并簡要說明如何獲得具有最佳自由距離的卷積碼。

解：最佳自由距離卷積碼的定義：對于相同的碼率R和相同的電路復雜性(存儲單元總

數m等)的各種卷積碼，使得自由距離d;最大的編碼稱為最佳自由距離(OFD,0PtimalFree

Distance)碼。

為了得到各種OFD碼，通常采用計算機搜索的方法，即對于給定的存儲單元總數m所

有可能的卷積碼編碼器,首先排除惡件卷積碼,然后對應每一-可能的卷積碼編碼器求其自由

距離d,逐?比較得到自由距離d;最大者即為最佳自由距離卷積碼編碼器。

二、綜合題(開卷部分，每題10分，共60分。閉卷部分交卷后方可參閱參考資料)

1.某通信系統的信源輸出僅有2個符號a、b,擬采用Lempel-Ziv編碼后送信道傳輸，

若某次通信需傳輸的符號序列為"aaaaaaahbbbhbhaaaaaaaabbbbhhbabaaaaaabbbbbbh

aaaaaaaaaaaaaaaaabM,請給出其Lcmpcl-Ziv編碼結果并簡要說明該編碼的性能。

解：

編碼結果

編碼包<0,7,b><1,6,a><15,15,b><15,14,a><1,15,b>

內容

aaaaaaabbbbbbbaaaaaaaabbbbbbbabaaaaaabbbbbbbaa

aaaaaaaaaaaaaaab

碼段符號87161516

數

如果把a、b看作為1、0,對編碼結果(即每個編碼包)可以用4+4+l=9-bil表示，傳

輸該序列用5個編碼包即45-bit,而該序列有62-bit,因此該編碼起到壓縮作用。

2.若題1信源符合a、b的出現概率分別為0.9和0.1,擬對其采用3重擴展后再進行

霍夫曼編碼，請給出編碼過程及結果，并求該種信源編碼的效率。

解：

aaa:0.729aab:0.081aba:0.081abb:0.009baa:0.081bab:0.009bba:

0.009bbb:0.001

設aaa、aab、...bbb分別為xI、x?、…xg,按照概率大小依此排列，有

XI

X2

X3

具體編碼過程、結果、編碼效率一略。

3.為了在有噪信道中獲得可靠的通信，擬對題2的霍夫曼編碼結果再進行信道編碼，

若霍夫曼編碼的輸出序列為aabbbaaabababbaabbbaabbbabab…，試給出采用戈萊碼(23,

12)編碼的第一個碼字；如果信道編碼不是采用戈萊碼而是采用縮短的BCH(120,78)編

碼，試給出構造該種編碼的生成多項式的方法以及縮短的方法，分析其糾錯和檢錯能力，簡

述其編碼和譯碼過程。

解：

44242

(1)對戈萊碼(23,12)采用生成多項式為g(x)=x+x°+x+x+x+x+1,即

110001110101

令a=l,b=0,則要編碼的序列為1100011101010011000110001010…；由于戈萊

碼是非本原BCH碼，其編碼規則與BCH碼相同，現采用系統碼，第一個碼字的編碼過程

如下：

11000111010100000000000

110001110101

00000000000

因此第一個戈萊碼脩字為11000111010100000000000,即監督位為全0(11位)。

(2)縮短的BCH(120,78)原碼為BCH(127,85),構造該種編碼的生成多項式，

可以由

g(x)=LCM{(p1(x)+q>2(x)+(p3(x)x6.+(p2r(x)

對于本題，127=216,(x)是GF(2?)上的元素a'的最小多項式，求出a、a3sa\a7的最小

多項式，將它們相乘即得到該種編碼能夠糾5個錯的生成多項式(次數為127-85=42)。

縮短的方法取原碼RCH(1?7.85)中的一個子集，其消息位的前7位均為0,編碼方

法與原碼相同，只是傳輸時前7位0不要傳送。

由求其生成多項式的過程已知該種編碼的原碼能夠糾5個隨機錯誤，至少能夠檢測10

個隨機錯誤，由于其監督位的個數位42,它能夠檢測42個突發錯誤并依概率檢測大于42

個突發錯誤。

其編碼方法上面已經說明，可以采用系統碼的編碼方法，只是傳輸時前7位0不要傳

送。

解碼時通常先補上縮短的0的位數，再按照原碼的譯碼方法進行譯碼，通常采用伴隨

式譯碼方法。即：先求出接收序列的伴隨式；然后根據作隨式求錯誤位置.，本題用杳表法將

很復雜，擬采用錯誤位置多項式的方法來求錯誤位置；得到錯誤位置后糾正之。

4.假設對題2的霍夫曼編碼輸出進行卷積編碼，采用的卷積碼編碼器為(3,1,2),

請給出你設計的卷積碼編嗎器并說明其是最佳自由距離卷積碼，用狀態圖方法給出輸入序列

(aabbabab...)的編碼輸出和用網格圖方法給出接收序列(abaabbaabbaaabbaba...)的

譯碼輸出。

解：

可以將教材中圖12.7變成系統卷積碼，說明它不是惡性卷積碼并通過與其他各類抽頭

方式比較知它的自由距離為最大，故是最佳自由距離卷積碼。

具體的編碼器、狀態圖、網格圖一略。

5.(1)試根據香農第二定理說明為什么交織雖然沒有注入冗余度但卻提高了糾突發錯

誤能力；(2)試給出利用信息加密技術進行保密通信的系統框圖(加密信道模型)并簡述其

工作原理，說明為什么非通信對像雖然收到了密文但在不能成功破譯時其獲得的信息量為

0.

解：(D設交織深度為A,則交織的結果等效為編碼長度擴大了'倍，其禁用碼組與許用碼

組之比也擴大了人倍，根據香農第二定理，在R<C情況下，碼長越長其糾、檢錯的能力應

該越強。

(2)信息加密技術進行保密通信的系統框圖如圖所示(教材圖14.1)。

其工作原理為：明碼文本M利用密鑰,通過某種可逆變換Ex加密成密文C,即C二Ek

(M);密文通過不安全的或公共信道進行傳輸，在傳輸過程中可能出現密文截取(截取密

文又稱為攻擊或入侵)，蘭合法用戶得到C后，用逆變換Dx二Ex'進行解密得到原來的明碼

文本消息，即D(C尸E[E(M)]=M;參數K是由碼元或字符組成的密鑰，它規定了

密碼變換集合中特定的一種加密變換Ek.

1_?密碼破矛一?M

截「-----

發端收端

朋劉」密WJ1------------A解密-法D——?

!

公共信道'~-T-~~M=Dx=Ex(C)

安全信道K

密鑰

圖14.1加密信道模型

非通信對像收到了密文但在不能成功破譯時，其不確定性集合中的元素沒有任何變化，

根據自信息量和平均互信息量的定義，他所獲得的信息量為0。

6.試從收、發雙方聯合優化的出發點來說明為什么信源編碼通常其編碼較為復雜而信

道編碼通常其譯碼較為復雜的原因。

解：

通常信源編碼的信道基本符號數目較少，而根據收發聯合優化的考慮，克服信道產生

的影響(對數字通信而言主要表現在誤碼上)主要由信道編碼完成，故對信源譯碼沒有提出

糾錯或檢錯的要求，因此在收端有一個與發端完全相同的信道基本符號集合就足以完成譯

碼；因為單譯可譯的編碼工作在發端完成而收端只要按照編碼規則對收到的碼進行比對就可

以了，因此通常編碼比譯碼要復雜些。

對于信道編碼，選定編碼規則后，編碼所要處理的主要是消息序列(把消息序列映射為碼字)，

以分組碼為例共2*個；而譯碼需要處理的是所有可能接收到的序列(仍以分組碼為例則共

有2“個)，考慮到信道的復雜性，譯碼均依從最大似然有則，故其比對過程比編碼的映射運

算復雜很多。

1.在無失真的信源中，信源輸出由___幽_來度量；在有失真的信源中，信源輸出由

R(D)來度量。

2.要使通信系統做到傳輸信息有效、可靠和保密，必須首先一信源編碼,

然后加密.編碼，再.信道編碼，最后送入信道。

3.帶限AWGN波形信道在平均功率受限條件下信道容量的基本公式,也就是有名的香農公

式是C=Wlog(l+SNR)：當歸一化信道容量C/W趨近于零時，也即信道完全喪失了通

信能力，此時E/N。為-L6dB.我們將它稱作香農眼,是一切編碼方式所能達到的理

論極限。

4.保密系統的密鑰量越小，密鑰端H(K)就越生_其密文中含有的關于明文的信息量/(M;

C)就越大。

5.已知n=7的循環碼g(x)=x4則信息位長度k為，校驗多項式

KMX斗X+1。

6.設輸入符號表為X={0,1},輸出符號表為Y二{0,1}。輸入信號的概率分布為p=(l/2,

1/2),失真函數為d(O,O)=d(l』)=0,d(0,1)=2,d(l,0)=1,則Dmin=o,R(Dni川

=Ibit/symbol、相應的編碼器轉移概率矩=0.5,R(Dmax)=

0,相應的編碼器轉移概率矩R67川:

LJ

7.已知用戶A的1<5人公開密鑰911)=(3,55)嚴5川=11,則。(n)=40，他的秘密

密鑰(d,n)=Q?應若用戶B向用戶A發送m=2的加密消息，則該加密后的消息為

二、判斷題

L可以用克勞夫特不等式作為唯一可譯碼存在的判據。(J)

2.線性碼一定包含全零碼。(V)

3.算術編碼是一種無失真的分組信源編碼，其基本思想是將一定精度數值作為序列的

編碼，是以另外一種形式實現的最佳統計兀配編碼。(X)

4.某一信源，不管它是否輸出符號，只要這些符號具有某些概率特性，就有信息審:。

（X）

5.離散平穩有記憶信源符號序列的平均符號墉隨著序列長度L的增大而增大。（義）

6.限平均功率最大焙定理指出對于相關矩陣一定的隨機矢量X,當它是正態分布時具

大燧。（J）

7.循環碼的碼集中的任何一個碼字的循環移位仍是碼字。（J）

8.信道容量是信道中能夠傳輸的最小信息量。（X）

9.香農信源編碼方法在進行編碼時不需要預先計算每個碼字的長度。（X）

10.在已知收碼R的條件下找出可能性最大的發碼C,作為譯碼估計值，這種譯碼方

法叫做最佳譯碼。（V）

三、計算題

某